Binomial Heaps

(The python code for this article is available here)

The standard binary heaps that everyone learns as part of a first algorithms course are very cool. They give guaranteed n sorting cost, can be stored compactly in memory since they’re full binary trees and allow for very fast implementations of priority queues. However, there are a couple of operations that we might be interested in that binary trees don’t give us, at least not cheaply.

In particular, we might be concerned with merging two heaps together. Say, for example, that we’re shutting down a processor with its own priority queue for schedulable processes, and we want to merge the workload in with another processor. One way to do this would be to insert every item in the first processor’s queue into the receiving processor’s queue. However, this takes O(n) time – at least, depending on how the queues are implemented. We’d like to be able to do that more efficiently.

Step forward binomial heaps. Binomial heaps are rather different to binary heaps – although they share a few details in common. Binomial heaps allow us to merge two heaps together in O(\log n) time, in return for some extra cost when finding the minimum. However, extracting the minimum still takes O(\log n), which is the same as a binary heap.

Continue reading

Computer Science Course Notes

I’m collecting a list of good courses in fundamental computer science,
mostly advanced algorithms courses. The aim is to filter out less
interesting or lower quality courses with poorer teaching materials, and
to make a reference for further study.

None of this would be hard to find with a quick search, but hopefully
the ‘goodness’ filter will add some value. For that reason, I’m posting
the link here. Suggestions – particularly for advanced systems topics –
very welcome!

Computer science course notes