PCPlus 271: Binary heaps

I 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.

PCPlus logo This time, the topic is one of my favest data structures ever: the binary heap, the structure of choice for priority queues everywhere. A great data structure with some absolutely awesome algorithms invented by one of the most brilliant computer scientists, Robert W. Floyd. Enough superlatives for you?

Really, I kid you not. I love this data structure. I can write about and implement it at the drop of a hat; no need for extra research (so I imagine I was getting close to the deadline for this article and needed to write something quickly). Weirdly, people ask me more about harder data structures — red-black trees as a notorious example — and not about this simple, fine data structure. An implementation of this (and a hash table) was the main reason people downloaded (and continue to download) my data structures library for Delphi, EZDSL.

This article first appeared in issue 271, August 2008.

You can download the PDF here.

Now playing:
Crowded House - Don't Dream It's Over
(from Recurring Dream, Best Of Crowded House)


Loading similar posts...   Loading links to posts on similar topics...

1 Response

#1 Dew Drop – August 20, 2009 | Alvin Ashcraft's Morning Dew said...
20-Aug-09 6:06 AM

Pingback from Dew Drop – August 20, 2009 | Alvin Ashcraft's Morning Dew

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response