Learning Functional Data Structures and Algorithms

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(log_n).

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