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. ...