Violation Heap

Violation heap is a relaxed mergeable priority queue data structure within computation and algorithms that achieves the optimal amortized time complexity of a Fibonacci heap while lowering per-node pointer storage and structural maintenance overhead. Introduced by Amr Elmasry at the 2008 International Computer Science Symposium in Russia (CSR) and published in Discrete Mathematics, Algorithms and Applications in 2010, the violation heap supports Find-Min, Insert, Meld, and Decrease-Key in O(1) amortized time and Delete-Min (along with arbitrary Delete) in O(log n) amortized time on an n-element heap. Rather than cutting subtrees whenever a second child is lost and maintaining four pointers plus a mark bit per node, a violation heap represents heap-ordered trees using a three-pointer child–sibling scheme, designates only the two most recently attached children of each node as active children, and permits temporary deviations from its local rank formula—termed violations—to be repaired via integer rank decrements and a three-way linking primitive.

By confining structural updates during Decrease-Key to active nodes and replacing binary tree consolidation with three-way root linking during Delete-Min, the violation heap ensures that every tree of rank r contains at least F_r+2 ≥ φ^r = e^{r ln φ} nodes (where φ = (1 + √5) / 2 ≈ 1.61803 is the golden ratio) while executing fewer pointer writes in network optimization algorithms such as Dijkstra's algorithm and Prim's algorithm for the minimum spanning tree problem.

Following Michael L. Fredman and Robert E. Tarjan's invention of the Fibonacci heap in 1984, algorithm researchers sought priority queue representations that retain O(1) amortized Decrease-Key without the empirical overhead of maintaining circular doubly linked child lists at every tree level. In a classic Fibonacci heap, each node stores four structural pointers—parent, first child, left sibling, and right sibling—together with an integer rank and a Boolean mark bit. Whenever Decrease-Key violates heap order between a node x and its parent y, x is spliced out of y's doubly linked child list and moved to the root list, potentially triggering cascading cuts upward through marked ancestors.

Subsequent structures explored diverse ways to streamline this machinery:

• The pairing heap eliminates rank fields and mark bits in favor of two-pass pairing during Delete-Min, achieving strong practical speed at the cost of a higher theoretical bound for Decrease-Key.
• The rank-pairing heap of Haeupler, Sen, and Tarjan (2011) and the hollow heap of Hansen, Kaplan, Tarjan, and Zwick (2015) relax rank differences or replace tree cuts with directed acyclic graph (DAG) second-parent links, while the quake heap maintains tournament trees with height-bounded rebuilding and the radix heap exploits monotone integer key buckets.
• Ahead of these later developments, Driscoll, Gabow, Shavlak, and Tarjan introduced the relaxed heap (1988), which permitted key-order violations inside binomial trees instead of cutting subtrees, and Tadao Takaoka introduced the 2–3 heap (1999).

Elmasry's violation heap synthesizes the best attributes of relaxed heaps and Fibonacci heaps: heap order is always preserved on every tree edge, while rank invariants are relaxed at non-active nodes and repaired through integer rank decrements and three-way linking rather than cascading ancestor cuts.

A violation heap represents a priority queue of n elements as a forest of heap-ordered trees whose roots are connected in a circular singly linked root list. The root with the minimum key sits at the head of this circular list (pointed to by the heap handle H), and its successor in the circular list points to the second root, enabling O(1) access to the minimum element and O(1) list concatenation or root insertion just after the minimum root.

Three-Pointer Child–Sibling Encoding

Every node x in a violation heap stores a key key(x), an integer rank r(x) ≥ 0, and three structural pointers (child, next, and prev), whose semantics depend on a node's position in its sibling list:

1. First Child Pointer (child): For any node x, child(x) points to the last (most recently joined) child of x, or null if x is a leaf.
2. Predecessor Sibling Pointer (prev): Inside the child list of a parent p, the children are ordered by the time they were linked to p. For every child y of p, prev(y) points to the preceding (older) sibling in p's child list, or null for the oldest child.
3. Successor Sibling or Parent Pointer (next): For every child y other than the last child of p, next(y) points to the next (newer) sibling in p's child list. For the last child z₁ of p (the child pointed to by child(p)), there is no newer sibling; therefore, next(z₁) points directly back to its parent p. For roots in the top-level circular root list, next links the roots around the circle while prev is unused.

This overloaded child–sibling representation stores three pointers per node instead of the four required by a standard Fibonacci heap while still allowing any of the last two children of a node p to locate p in O(1) time: the last child z₁ follows next(z₁) = p, and the second-to-last child z₂ follows next(next(z₂)) = next(z₁) = p.

Active Nodes vs. Inactive Nodes

In a violation heap, the children of any node x are partitioned into two structural classes according to their position in x's child list:

• Active Children: The last two children of x—the most recently joined child z₁ = child(x) and the second most recently joined child z₂ = prev(z₁)—are designated the active children of x. Any missing active child is treated as an empty dummy child of rank −1.
• Inactive Children: All earlier children of x preceding z₂ in the sibling list are inactive children; likewise, all roots in the root list are inactive.

Because only the two newest children of any parent are active, detaching an inactive node u during Decrease-Key never alters the active children of u's parent and cannot disturb its parent's rank formula. Moreover, because u is not the last child, next(u) points to a newer sibling w, enabling u to be spliced out of the doubly linked prefix of the sibling list in O(1) worst-case time without consulting its parent at all.

Definition of the Rank Invariant

Every node x in a violation heap maintains an integer rank r(x) ≥ 0. Let z₁ and z₂ denote the two active children of x, with ranks r(z₁) and r(z₂) (where any nonexistent active child is assigned rank −1). The violation heap enforces the following Rank Invariant on every node x:

r(x) = ⌈ (r(z₁) + r(z₂)) / 2 ⌉ + 1

Equivalently, the sum of the ranks of the two active children of x satisfies:

2 r(x) − 3 ≤ r(z₁) + r(z₂) ≤ 2 r(x) − 2

For example, a leaf x has two missing active children of rank −1, so r(x) = ⌈ (−1 + (−1)) / 2 ⌉ + 1 = 0. A node x with one active child of rank 0 and one missing active child of rank −1 has r(x) = ⌈ (0 − 1) / 2 ⌉ + 1 = 1.

Subtree Size Lower Bound and Golden-Ratio Rank Bound

The Rank Invariant implies that any subtree rooted at a node x of rank r contains at least F_r+2 nodes, where F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, ... is the Fibonacci sequence. Whenever x advances from rank k − 1 to rank k, a new child becomes the latest active child z₁ of x, pushing the previous second active child into the inactive list. Under the Rank Invariant, when a node x reaches rank r, its sequence of children ordered by join time has ranks at least 0, 0, 1, 2, ..., r − 2, or its two active children have ranks summing to at least 2r − 3 (such as r − 1 and r − 2). By induction on r, the minimum number of descendants S(r) of a node of rank r satisfies:

S(r) ≥ S(r − 1) + S(r − 2) ≥ F_r+2 ≥ φ^r = e^{r ln φ}

Consequently, in an n-element violation heap, no node's rank can exceed r(x) ≤ ⌈ log_φ n ⌉ ≈ 1.4404 log₂ n.

Find-Min, Insert, and Meld in O(1) Worst-Case Time

• Find-Min(H): Returns the key and item at the head root of the circular root list in O(1) worst-case time.
• Insert(H, x): Initializes r(x) = 0, child(x) = null, inserts x into the circular root list of H just after the minimum root, and updates the head pointer of H if key(x) is smaller than the current minimum key in O(1) worst-case time.
• Meld(H₁, H₂): Splices the two circular singly linked root lists together in O(1) worst-case time and sets the merged heap handle to the root with the smaller minimum key.

Three-Way Linking Primitive

Unlike binomial heaps, Fibonacci heaps, and hollow heaps—which link two trees of equal rank r to form a tree of rank r + 1—the Rank Invariant r(x) = ⌈ (r(z₁) + r(z₂)) / 2 ⌉ + 1 means that attaching a single new active child of rank r to a root u whose existing newest active child has rank ≤ r − 2 might not raise R(u) to r + 1. To guarantee that the winning root attains two active children of rank r (and therefore satisfies r(u) = ⌈ (r + r) / 2 ⌉ + 1 = r + 1), a violation heap uses three-way linking:

Given three roots u, v, and w such that at least two of them (u and v) have equal rank r, and the third root w also has rank r (or ≤ r when merging violations):

1. Compare the keys of the two equal-rank roots u and v so that the root with the smaller key—say u—is chosen as the new parent.
2. Attach v and w as the two newest active children of u by prepending both to child(u), shifting the previous active children of u into the inactive prefix of u's child list.
3. Increment r(u) to r + 1.

Delete-Min(H) via Three-Way Consolidation in O(log n) Amortized Time

When Delete-Min(H) removes the minimum root m:

1. Root Removal and Child Promotion: Remove m from the circular root list and detach each child of m, inserting all of m's children into the root list as independent roots.
2. Rank-Indexed Bucket Consolidation: Maintain a rank-indexed table A[0 .. ⌈log_φ n⌉], where each slot A[r] holds up to two roots of rank r. For each root x in the root list:
   • While slot A[r(x)] already contains two roots y and z of rank r = r(x), remove y and z from A[r], perform a three-way link among x, y, and z to form a root of rank r + 1, and continue at slot r + 1.
   • Once A[r(x)] contains fewer than two roots, store x in A[r(x)].
3. Root List Reconstruction: After all roots are processed, at most two roots remain at each rank r ∈ {0, 1, ..., ⌈log_φ n⌉}. Link these ≤ 2⌈log_φ n⌉ + 2 roots back into a circular singly linked list with the new minimum root at the head of H.

Decrease-Key(H, x, k) and Stopping Rank-Violation Propagation

When the key of a node x is decreased to k < key(x):

1. Update key(x) ← k. If x is already a root, update the head pointer of H if k is smaller than the current minimum and terminate in O(1) time.
2. If x is an inactive child, splice x out of its sibling list using prev(x) and next(x) in O(1) worst-case time and insert x into the circular root list. Because no active child of x's parent changed, zero rank updates propagate upward.
3. If x is an active child of p, cut x to the root list (or swap x with an inactive child/root) and recalculate the target rank R(p) = ⌈ (r(z₁) + r(z₂)) / 2 ⌉ + 1 of p and its active ancestors. Whenever an ancestor y's rank drops from r to r − 1:
   • If y is a root or an inactive child, rank propagation stops.
   • If y is an active child whose parent q had an even sum of active-child ranks before r(y) dropped by 1, the ceiling formula ⌈ (2m − 1) / 2 ⌉ + 1 = m + 1 leaves r(q) unchanged, so propagation stops at q (or when two equal-rank violations are merged via three-way linking).

Define the potential function Φ(H) = t(H) + 2 ∑_{x ∈ H} r(x) + b(H), where t(H) is the number of trees in the root list and b(H) counts parent nodes whose two active children have an odd rank sum. Each step of rank-decrement propagation during Decrease-Key decreases an ancestor's rank r(y) by at least 1, releasing 2 units of potential from 2 ∑ r(x) to pay for the O(1) pointer and rank update, while stopping at the first ancestor whose active-child rank sum was even (increasing b(H) by at most 1). Moreover, because a node m only acquires new children when its rank increases by 1 during a three-way link (attaching two active children per rank increment), m has at most 2 r(m) ≤ 2 ⌈log_φ n⌉ children, bounding Delete-Min in O(log n) amortized time.

Why does a violation heap use three-way linking instead of two-way linking during Delete-Min?

In a violation heap, the rank of a node u is determined by its two newest (active) children z₁ and z₂ via r(u) = ⌈ (r(z₁) + r(z₂)) / 2 ⌉ + 1. Because rank decrements during Decrease-Key can leave a root u of rank r whose current active children have ranks smaller than r − 1, linking only one other root v of rank r to u might not give u two active children whose ranks sum to at least 2r − 1. Linking three roots u, v, w of rank r gives the winner u two fresh active children v and w both of rank r, setting r(u) = ⌈ (r + r) / 2 ⌉ + 1 = r + 1 regardless of u's prior children.

How can an inactive child be detached in O(1) time if it has no parent pointer?

In the three-pointer child–sibling representation of a violation heap, the children of a parent p are linked via prev (older sibling) and next (newer sibling), with child(p) pointing to the newest child z₁ and next(z₁) pointing to p. Because an inactive child u is never one of the two newest children z₁ or z₂, u always has a newer sibling next(u) ≠ p. Detaching u simply sets prev(next(u)) ← prev(u) and (if prev(u) ≠ null) next(prev(u)) ← next(u), without reading or modifying p.

Why is the maximum degree of a node in a violation heap at most 2⌈log_φ n⌉?

A node x only acquires new children when it wins a three-way link during Delete-Min consolidation, and each three-way link attaches two new active children to x while incrementing r(x) by 1. Even if x's rank is later decremented due to Decrease-Key operations on its active children, the number of remaining children of x never exceeds twice its rank 2 r(x) ≤ 2 ⌈log_φ n⌉.

1. Elmasry, A. (2010). "The Violation Heap: A Relaxed Fibonacci-Like Heap." Discrete Mathematics, Algorithms and Applications, 2(4), 493–503. https://doi.org/10.1142/S1793830910000838
2. Elmasry, A. (2008). "The Violation Heap: A Relaxed Fibonacci-Like Heap." In Computer Science – Theory and Applications (CSR 2008), Lecture Notes in Computer Science, vol. 5010, pp. 159–166. Springer. https://doi.org/10.1007/978-3-540-79709-8_18
3. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
4. Driscoll, J. R., Gabow, H. N., Shavlak, R., & Tarjan, R. E. (1988). "Relaxed Heaps: An Alternative to Fibonacci Heaps with Applications to Parallel Computation." Communications of the ACM, 31(11), 1343–1354. https://doi.org/10.1145/50087.50096
5. Haeupler, B., Sen, S., & Tarjan, R. E. (2011). "Rank-Pairing Heaps." SIAM Journal on Computing, 40(6), 1463–1485. https://doi.org/10.1137/100785351