(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 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 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 time, in return for some extra cost when finding the minimum. However, extracting the minimum still takes , which is the same as a binary heap.