Binomial Heaps and Skew Binomial Heaps.
Rene Meis, Finn Nielsen, Peter Lammich · 2010
We implement and prove correct binomial heaps and skew bino-mial heaps. Both are data-structures for priority queues. While bi-nomial 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 of Brodal and Okasaki [1].