The Fishspear priority queue algorithm – Arthur O'Dwyer – Stuff mostly about C++

I continue participating in Zartaj Majeed’s book club on Knuth’s The Art of Computer Programming, previously mentioned in “Bubblesort, rocksort, cocktail-shaker sort” (2020-12-13). The past couple of weeks, we’ve been looking at section 5.2.3, “Sorting by selection,” in which the problem of repeatedly selecting the max element leads Knuth to investigate priority queues.

So far, Knuth discusses basically four kinds of priority-queue data structures: the sorted list, the classic random-access-array-based heap, the unbalanced binary heap (specifically the leftist tree, although in the third edition he describes leftist trees as “already obsolete”), and the balanced binary search tree (such as an AVL or red-black tree; he defers this to section 6.2.3). But he gives (on page 152) pointers to many other ideas from the literature: stratified trees, binomial queues, pagodas, pairing heaps, skew heaps, Fibonacci heaps, calendar queues, relaxed heaps, fishspear, hot queues, “etc.”

I was intrigued by the name of the Fishspear data structure, so I went looking for that paper (M. J. Fischer and M. S. Paterson, JACM 41 (1994), 3–30) and found it — or something close enough to it, anyway. It turns out to be a data structure that looks like this:

Leave a Comment