You might have thought that the last couple of posts would have done it for the priority queue – after all, we have the optimal heap implementation for it – but no. There are a couple more fun bits. Let’s investigate a little bit more. […]
READ MORELast time, we introduced the concept of a priority queue data structure, and illustrated it with a couple of simple implementations using an array: firstly by adding new items at the end, and then getting the highest priority item by searching through the array; secondly by maintaining the array in sorted order by priority, forcing new items to be inserted in the correct position in the array, and getting an item is merely removing it from the end of the array. I called these fast insertion/slow deletion and slow insertion/fast deletion implementations. […]
READ MOREFirst up in my “reprints from The Delphi Magazine, cast in JavaScript” posts must be the priority queue. It is after all, an important data structure, can be implemented quickly (although perhaps in not a very efficient manner), and introduces an excellent algorithm, the heap. […]
READ MOREI write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a few months. When I buy the current issue, I'll publish the article from the issue a year ago. Since I've now got August's issue (and have had it for a couple of weeks), here's August 2008's article. […]
READ MORE