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 when 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+)

• BinomialHeap.java
• BinomialHeapTest.java (JUnit)

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

• binomialheap.py
• binomialheap-test.py

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

C++ (C++14 and above)

• BinomialHeap.hpp
• BinomialHeapTest.cpp

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.

Rust

• binomialheap.rs
• binomialheap-test.rs

This is modeled after std::collections::binary_heap::BinaryHeap, but this is a min-heap whereas the standard library is a max-heap. A move iterator is supported.

License: MIT (open source)

More info

• Wikipedia: Binomial heap
• David Galles: Data Structure Visualizations - Binomial Queue