Project Nayuki

Binomial heap

The binomial heap data structure implements a priority queue. Arbitrary elements are added to the heap (i.e. queue), and at any time the minimum element can be removed. Additionally, a binomial heap can move all of its elements into another heap (merging). All of these individual operations take O(log n) time, where n is the number of elements in the heap.

I first implemented this data structure in university 2nd year in a computer science algorithms course. Though there are many implementations by others published online, the reason I’m publishing mine is because searching on the web, the code I saw was messy, not generic, or possibly containing subtle bugs. I hope my code will be useful for people looking to understand the algorithm and those extending my work.

Source code


The class implements the java.util.Queue interface, so it can be used as a drop-in replacement of PriorityQueue as long as iterator() is not called. The maximum queue size is unlimited, but size() will throw an exception above Integer.MAX_VALUE.


This implementation only supports the methods {enqueue(), dequeue(), peek(), merge(), clear()} and the built-in function len(). Compatible with Python 2 and 3.


The class is modeled after the Java version, supporting the methods {size(), enqueue(), dequeue(), peek(), merge(), clear()}. It’s similar to the features provided by std::priority_queue. Requires C++11.

License: MIT (open source)

More info