Chapter 12. Binomial Heaps
In Chapter 8, Queues we looked at binary heaps. Now a binary min-heap takes the form of a complete binary tree. This means the key at each node is less than or equal to its children.
We will look at one more popular heap implementation, namely a binomial heap. A binomial heap is a collection of binomial trees, giving us a very efficient heap-merging operation.
We will begin with an introduction to binomial trees. Next, we will see how to link two binomial trees, the basics for growing a heap. The process of inserting into a binomial heap exhibits a surprising coincidence to the binary number addition process. This detour will help us understand the merge algorithm.
Next, we will look at how to merge two binomial heaps.
Finally, we will look at how to find and delete a minimum element. As we move on, we will reason the code and eventually exercise the various operations on REPL. We will do all this in good time, though. Let's review some basic terminologies...
