We introduce an adaptation of run-relaxed heaps which provides efficient heap operations with respect to the number of element comparisons performed. Our data structure guarantees the worst-case cost of O(1) for find-min, insert, and decrease; and the worst-case cost of O(lg n) with at most lg n + 3 lg lg n + O(1) element comparisons for delete, improving the bound of 3 lg n + O(1) on the number of element comparisons known for run-relaxed heaps. Here, n denotes the number of elements stored prior to the operation in question, and lg n equals max{1, log₂ n}.

@inproceedings{EJK2006cC,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Two-tier relaxed heaps},
  booktitle = {Proceedings of the 17th International Symposium on Algorithms
    and Computation},
  series = {Lecture Notes in Computer Science},
  volume = {4288},
  publisher = {Springer-Verlag},
  year = {2006},
  pages = {308--317},
}