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

Java (SE 5+)

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.

Python (compatible with 2 and 3)

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

C++ (C++11 and above)

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.

License: MIT (open source)

More info