A weak heap is a priority queue that supports the operations construct,
minimum, insert, and extract-min. To store n elements, it uses
an array of n elements and an array of n bits. In this paper we
study different possibilities for optimizing construct and insert such
that minimum and extract-min are not made slower. We provide a
catalogue of algorithms that optimize the standard algorithms in
various ways. As the optimization criteria, we consider the worst-case
running time, the number of instructions, branch mispredictions, cache
misses, element comparisons, and element moves. Our contributions are summarized as follows:

1.
The standard algorithm for construct runs in O(n) worst-case time
and performs n − 1 element comparisons. Our improved algorithms
reduce the number of instructions, the number of branch mispredictions,
the number of element moves, and the number of cache misses.

2(a)
Even though the worst-case running time of the standard
insert algorithm is logarithmic, we show that—in contrast to binary heaps—n
repeated insert operations require at most 3.5n + O(lg^{2}n) element comparisons.

2(b)
We improve a recent result of ours,
in which we achieve O(1) amortized time per insertion, to
guarantee O(1) worst-case time per insertion.
After the deamortization, minimum still takes O(1)
worst-case time and involves no element comparisons, and
extract-min takes O(lg n) worst-case time and involves at most
lg n + O(1) element comparisons. This constant-factor optimality
concerning the number of element comparisons has previously
been achieved only by pointer-based multipartite priority queues.

We have implemented most of the proposed algorithms and tested their practical behaviour.
Interestingly, for integer data, reducing the number of branch mispredictions
turned out to be an effective optimization in our experiments.

@article{EEK2013J,
author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
title = {Weak heaps engineered},
journaltitle = {Journal of Discrete Algorithms},
volume = {23},
year = {2013},
pages = {83--97},
}