We give a priority queue that guarantees the worst-case cost of Θ(1) per minimum finding, insertion, and decrease; and the worst-case cost of Θ(lg n) with at most lg n + O(√lg n) element comparisons per deletion. Here, n denotes the number of elements stored in the data structure prior to the operation in question, and lg n is a shorthand for max{1, log₂ n}. In contrast to a run-relaxed heap, which allows heap-order violations, our priority queue relies on structural violations. By mimicking a priority queue that allows heap-order violations with one that only allows structural violations, we improve the bound on the number of element comparisons per deletion to lg n + O(lg lg n).

@inproceedings{EJK2007C,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {On the power of structural violations in priority queues},
  booktitle = {Proceedings of the 13th Computing: The Australasian Theory
    Symposium},
  series = {Conferences in Research and Practice in Information Technology},
  volume = {65},
  publisher = {Australian Computer Society, Inc.},
  year = {2007},
  pages = {45--53},
}