• 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² 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.

@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},
}