PCPlus 271: Binary heaps

15 years ago

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.

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)