Binomial Heaps and Skew Binomial Heaps

Rene Meis 📧, Finn Nielsen 📧 and Peter Lammich 🌐

October 28, 2010

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

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

Topics

Theories of Binomial-Heaps