We present the first pointer-based heap implementation with time bounds matching those of
Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and …

Back in 1964 Williams introduced the binary heap as a basic priority queue data structure
supporting the operations Insert and ExtractMin in logarithmic time. Since then numerous …

We introduce the rank-pairing heap, an implementation of heaps that combines the
asymptotic efficiency of Fibonacci heaps with much of the simplicity of pairing heaps. Other …

The weak heap is a priority queue that was introduced as a competitive structure for sorting.
Its array-based form supports the operations find-min in O (1) worst-case time, and insert …

We give a priority queue that achieves the same amortized bounds as Fibonacci heaps.
Namely, find-min requires O (1) worst-case time, insert, meld and decrease-key require O (1) …

We introduce a data structure which provides efficient heap operations with respect to the
number of element comparisons performed. Let n denote the size of the heap being …

In typical applications, a priority queue is used to execute a sequence of n insert, m
decrease, and n delete-min operations, starting with an empty structure. We study the …

We consider the classical problem of representing a collection of priority queues under the
operations find-min, insert, decrease, meld, delete, and delete-min. In the comparison-based …

We introduce two numeral systems, the magical skew system and the regular skew system,
and contribute to their theory development. For both systems, increments and decrements …

We give a priority queue that achieves the same amortized bounds as Fibonacci heaps.
Namely, find-min requires O (1) worst-case time, insert, meld and decrease-key require O (1) …