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 manipulated. Our data structure guarantees the worst-case cost of O(1) for finding the minimum, inserting an element, extracting an (unspecified) element, and replacing an element with a smaller element; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for deleting an element. We thereby improve the comparison complexity of heap operations known for run-relaxed heaps and other worst-case efficient heaps. Furthermore, our data structure supports melding of two heaps of size m and n at the worst-case cost of O(min{lg m, lg n}).

@article{EJK2008aJ,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two-tier relaxed heaps},
  journaltitle = {Acta Informatica},
  volume = {45},
  number = {3},
  year = {2008},
  pages = {193--210},
}