Strengthened Lazy Heaps: Surpassing the Lower Bounds for Binary Heaps

Stefan Edelkamp, Jyrki Katajainen, Amr Elmasry

Let $n$ denote the number of elements currently in a data structure. An in-place heap is stored in the first $n$ locations of an array, uses $O(1)$ extra space, and supports the op…