Partition-based Simple Heaps

We introduce a new family of simple priority-queue data structures: partition-based heaps.

The structures consist of $O(\log n)$ doubly-linked lists; order is enforced among data in different lists, but the individual lists are unordered. Our structures have $O(\log n)$ amortized time extract-min and $O(\log \log n)$ amortized time insert and decrease-key.

The structures require nothing beyond binary search over $O(\log n)$ elements, as well as binary partitions and concatenations of linked lists in natural ways as the linked lists get too big or small. We present three different ways that these lists can be maintained in order to obtain the stated amortized running times.

History

The paper resulted from a triple merge of three similar data structures, developed independently. Casper Rysgaard and I contributed the LP Heaps as given in detail; they are a special case of lazy search trees with some simplifications when solely used as a priority queue.