O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required