We give a priority queue which guarantees the worst-case cost of Θ(1) per minimum finding, insertion and decrease (often called decrease-key), and the worst-case cost of Θ(lg n) with at most lg n + O(√lg n) element comparisons per minimum deletion and 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. The motivation comes from a recent paper by Kaplan and Tarjan, where they asked whether these two apparently different notions of a violation are equivalent in power.

@report{EJK2005bR,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {On the power of structural violations in priority queues},
  type = {CPH STL Report},
  number = {2005-3},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2005},
  pagetotal = {18},
}