Hollow Heap

Hollow heap is a mergeable priority queue data structure within computation and algorithms that represents heap-ordered hierarchies as a rooted directed acyclic graph (DAG) containing both item-bearing full nodes and itemless hollow nodes. Introduced by Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, and Uri Zwick at the 2015 International Colloquium on Automata, Languages, and Programming (ICALP) and published in the ACM Transactions on Algorithms in 2017, the hollow heap matches the optimal amortized analysis time bounds of a Fibonacci heap: O(1) amortized time for Insert, Find-Min, Meld, and Decrease-Key, and O(log n) amortized time for Delete-Min and Delete on an n-item priority queue. Unlike Fibonacci heaps, hollow heaps eliminate parent pointers, circular doubly linked sibling lists, node mark bits, and recursive cascading cuts, replacing tree surgery during Decrease-Key with lazy item migration and a single second-parent pointer per hollow node.

By simplifying the pointer updates required by Decrease-Key to constant worst-case work while deferring all structural reclamation to Delete-Min, hollow heaps reduce memory overhead per node and improve cache locality in shortest-path and minimum-spanning-tree routines such as Dijkstra's algorithm and Prim's algorithm.

Since Michael L. Fredman and Robert E. Tarjan introduced the Fibonacci heap in 1984, theoretical computer scientists sought a simpler priority queue that achieves O(1) amortized Decrease-Key without maintaining four pointers per node (parent, child, left sibling, right sibling) plus a Boolean mark bit. In a standard Fibonacci heap, decreasing the key of a node u requires cutting u from its parent v in a doubly linked child list; if v has already lost a child previously, a cascading cut propagates upward along parent pointers to preserve the exponential size lower bound F_r+2 ≥ φ^r = e^{r ln φ} on trees of rank r.

Although alternatives such as pairing heaps, rank-pairing heaps, violation heaps, and worst-case Brodal queues explored different trade-offs between pointer complexity and worst-case or amortized guarantees, all tree-based priority queues that cut subtrees on Decrease-Key must either maintain doubly linked child lists (to detach an arbitrary child in O(1) time) or encode parent links indirectly. Hollow heaps avoid detaching subtrees during Decrease-Key altogether: when an item's key decreases, the item vacates its existing node—leaving that node hollow in place—and moves into a newly allocated node carrying the updated key.

A hollow heap represents a collection of n items as a heap-ordered directed acyclic graph rooted at the minimum-key node h. Every node u in the DAG is classified into one of two states:

1. Full Node: A node u that currently holds an active item e (item[u] = e), where the item itself points back to its current host node (node[e] = u).
2. Hollow Node: A node u whose item has been deleted or moved to another node via Decrease-Key (item[u] = null). Once a node becomes hollow, it never becomes full again; it remains in the DAG temporarily to hold its remaining descendants together until it becomes a root and is destroyed during a subsequent Delete-Min or Delete operation.

Node Fields and Pointer Economy

Each node u in a single-root hollow heap stores five compact fields:

• item: A pointer to the stored element e (or null if u is hollow).
• key: The priority value k associated with u at the time its item was placed in u.
• child: A pointer to the head of a singly linked list of children of u.
• next: A pointer to the next sibling in the singly linked child list of u's primary parent.
• ep (second parent): An extra parent pointer that is null for every full node and for every hollow node created by Delete, and non-null at most once for a hollow node created by Decrease-Key.
• rank: A non-negative integer r ≥ 0 bounding the structural degree of u, stored in a single byte because r ≤ log_φ n (where φ = (1 + √5) / 2 ≈ 1.61803 is the golden ratio).

Children of a node u are linked in a singly linked list via child and next rather than a doubly linked list, and no node ever stores a pointer to its original first parent.

Ranked Links and Unranked Links

Edges in the hollow-heap DAG are directed from parent to child and satisfy the min-heap ordering invariant: if there is a directed edge from u to v, then key[u] ≤ key[v]. Two linking primitives combine roots u and v (assuming key[u] ≤ key[v], v becomes a child of u by prepending v to child[u]):

• Unranked Link: Applied during Meld and Insert to combine two roots of arbitrary rank without changing either node's rank.
• Ranked Link: Applied during Delete-Min consolidation to combine two roots u and v of equal rank r (rank[u] = rank[v] = r). The winner u increments its rank to r + 1 (rank[u] = r + 1), while the loser v becomes a child of u and retains rank r.

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

Because a non-empty hollow heap maintains its unique root h as a full node holding the global minimum key:

• Find-Min(H): Returns item[h] in O(1) worst-case time.
• Meld(H₁, H₂): Performs an unranked link between the two full roots h₁ and h₂, making the root with the larger key the first child of the root with the smaller key in O(1) worst-case time.
• Insert(e, k, H): Allocates a new full node u with item[u] = e, key[u] = k, rank[u] = 0, and links u with the root h via Meld in O(1) worst-case time.

Decrease-Key via Second-Parent DAG Edges

Suppose Decrease-Key(e, k, H) decreases the key of item e to a new value k < key[u], where u = node[e] is the full node currently holding e:

1. Root Case: If u is the root h of the heap, update key[u] = k in place in O(1) time; u remains full and no new node is created.
2. Non-Root Case: If u ≠ h, allocate a new full node v with item[v] = e, key[v] = k, move e into v (node[e] = v), and mark the old node u hollow (item[u] = null).
3. Rank Transfer and Second Parent Assignment: Set rank[v] = max(0, rank[u] − 2). In the two-parent representation analyzed by Hansen et al., v is made a second parent of u directly (ep[u] = v) while u retains its last two ranked children along its original child list, so that u now has two parents in the DAG: its original parent (via next in the original parent's child list) and its new parent v (via ep[u]). Finally, link the new root v with the heap root h via an unranked link.

All steps of Decrease-Key execute in O(1) worst-case time without traversing or modifying the child list of u's original parent.

Delete and Delete-Min via DAG Topological Destruction

When Delete(e, H) is called on an item e whose node u = node[e] is not the minimum root h, the algorithm sets item[u] = null and node[e] = null in O(1) worst-case time, turning u into a hollow node in place.

Reclamation of hollow nodes only occurs when the root itself becomes hollow (via Delete-Min(H) or Delete on the minimum element). During Delete-Min:

1. Hollow-Root Peeling: Maintain a list of hollow roots (initially containing h, which was just made hollow) and an array A[0 .. R] of full roots indexed by rank. While a hollow root u exists, destroy u and inspect each child w in child[u]:
   • If w has only one parent (ep[w] = null), w loses its sole parent and becomes a new root (added to the hollow-root list if w is hollow, or inserted into the rank-indexed table A if w is full).
   • If w has two parents (ep[w] ≠ null), clear ep[w] = null so that w now has one remaining parent in the DAG and does not yet become a root.
2. Ranked Consolidation of Full Roots: Whenever a full root w of rank r is inserted into A[r] and another full root y already occupies A[r], perform a ranked link between w and y to produce a root of rank r + 1, clear A[r], and repeat at slot r + 1.
3. Final Unranked Melding: Once all hollow roots have been eliminated, link the remaining ≤ R + 1 full roots in A[0 .. R] via unranked links to re-establish a single full root h.

In a hollow heap, every node of rank r acquires its children through r ranked links at ranks 0, 1, ..., r − 1. When a node u of rank r becomes hollow via Decrease-Key and gains a second parent v of rank r − 2, u retains its last two ranked children of ranks r − 2 and r − 1 along the path to its original parent. By induction on the sequence of links and hollowings, any node of rank r in a hollow heap with n full nodes has at least F_r+2 full descendants in the underlying DAG (where F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, ... are the Fibonacci numbers). Because F_r+2 ≥ φ^r, the maximum rank of any node satisfies r ≤ ⌊log_φ n⌋ ≈ 1.4404 log₂ n.

Using a potential function Φ that counts the number of full roots plus twice the number of hollow nodes currently in the DAG, each Insert increases Φ by 1, each Decrease-Key creates one hollow node (increasing Φ by at most 2), and each destruction of a hollow root during Delete-Min pays for its removal using the stored potential, yielding O(1) amortized time for Insert, Meld, and Decrease-Key and O(log n) amortized time for Delete-Min and Delete.

Why is a hollow heap a directed acyclic graph (DAG) instead of a tree?

When Decrease-Key is called on a non-root node u, the item moves into a newly created node v and leaves u hollow. Rather than cutting u out of its original parent's singly linked child list (which would require a parent pointer and doubly linked siblings), the hollow heap makes the new node v a second parent of the hollow node u via the extra pointer ep[u] = v. Because a hollow node can have up to two parents—its original parent and the node created when its item's key decreased—the underlying structure is a rooted DAG rather than a tree.

How can a hollow heap have more nodes than active items without running out of memory?

Every Decrease-Key operation allocates at most one hollow node. If an application caps the number of active hollow nodes or periodically rebuilds the heap whenever the total number of nodes exceeds a constant multiple (such as 2n or 3n) of the number of full nodes, the space complexity remains O(n) while preserving all O(1) and O(log n) amortized time bounds.

How does a hollow heap compare to a soft heap?

A hollow heap is a comparison-based priority queue that never alters keys and guarantees O(log n) amortized Delete-Min, which conforms to the Ω(n log n) comparison sorting lower bound. By contrast, Bernard Chazelle's soft heap achieves O(1) amortized time for all operations (including Delete-Min) at the cost of purposefully corrupting (increasing) the keys of up to εN items for an error parameter 0 < ε < 1, with amortized overhead O(log(1/ε)).

1. Hansen, T. D., Kaplan, H., Tarjan, R. E., & Zwick, U. (2017). "Hollow Heaps." ACM Transactions on Algorithms, 13(3), Article 42, 1–27. https://doi.org/10.1145/3093240
2. Hansen, T. D., Kaplan, H., Tarjan, R. E., & Zwick, U. (2015). "Hollow Heaps." In Automata, Languages, and Programming (ICALP 2015), Lecture Notes in Computer Science, vol. 9134, pp. 689–700. Springer. https://doi.org/10.1007/978-3-662-47672-7_56
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. 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