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

Summary

We looked at binomial heaps, which are heaps implemented using binomial trees. Binomial trees have a certain structure. They have an important property, a rank.

A binomial heap is composed of binomial trees, with the additional stipulation that every tree will have a distinct rank. The roots of a binomial tree are linked to a list in order of increasing rank, thereby forming a binomial heap. Every binomial tree in the heap adheres to the heap property.

We saw four major operations, namely insertion, merge, findMin, and removeMin. We saw how these operations have complexity of O(logn).

This is an interesting data structure and we invite you to compare it with the leftist heaps introduced earlier.

Let's continue the journey with a look at functional ...

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