Binomial Heaps and Skew Binomial Heaps

Rene Meis 📧, Finn Nielsen 📧 and Peter Lammich 🌐

October 28, 2010


We implement and prove correct binomial heaps and skew binomial heaps. Both are data-structures for priority queues. While binomial heaps have logarithmic findMin, deleteMin, insert, and meld operations, skew binomial heaps have constant time findMin, insert, and meld operations, and only the deleteMin-operation is logarithmic. This is achieved by using skew links to avoid cascading linking on insert-operations, and data-structural bootstrapping to get constant-time findMin and meld operations. Our implementation follows the paper by Brodal and Okasaki.


BSD License


Related publications

Session Binomial-Heaps