On the power of structural violations in priority queues

Abstract. 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 2 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. CR Classification. E.1 [Data Structures]: Lists, stacks, and queues; E.2 [Data