In computer science, a 2–3 heap is a data structure that implements a priority queue. It is a variation on the classic heap, introduced by Tadao Takaoka in 1999. The structure is closely related to the 2–3 tree and shares several design ideas with the Fibonacci heap, aiming to provide efficient amortized performance for common heap operations.
Definition and Structure
A 2–3 heap is an r‑nomial queue with $r = 3$; that is, it is an $(l,r)$-heap where $l = 2$ and $r = 3$. The heap is built from a collection of rooted trees that satisfy the following properties:
- Heap order – each node’s key is no larger (in a min‑heap) or no smaller (in a max‑heap) than the keys of its children.
- Tree composition – each tree is formed by repeatedly linking together either two or three sub‑trees of the same dimension, analogous to the way 2–3 trees combine nodes of degree 2 or 3.
- Polynomial representation – the collection of trees can be expressed as a polynomial of the form
$$ P = a_{k-1}T(k-1) + \dots + a_{1}T(1) + a_{0}T(0), $$
where each $T(i)$ denotes a tree of dimension $i$ and the coefficients $a_i$ satisfy $0 \le a_i \le 2$.
The arrangement of trees yields a workspace of nodes whose size is bounded between 4 and 9, which is used during restructuring operations.
Core Operations
| Operation | Amortized Cost | Description |
|---|---|---|
| Insert | $O(\log n)$ (amortized) | A new singleton tree $T(0)$ is merged into the existing polynomial. Carry‑over may propagate, similar to addition in base‑3, but the number of comparisons per level is constant. |
| Find‑minimum | $O(1)$ | The minimum key resides at the root of one of the trees; scanning the roots of at most three trees yields the minimum. |
| Delete‑minimum | $O(\log n)$ (amortized) | The tree containing the minimum root is removed, its children become separate trees, and the resulting set is merged back into the polynomial. |
| Decrease‑key | $O(\log n)$ (amortized) | The affected node may be cut from its tree and re‑inserted as a new root, followed by potential restructuring of the workspace. |
| Merge (union) | $O(\log n)$ (amortized) | Two 2–3 heaps are combined by merging their polynomial representations, handling carries as in base‑3 addition. |
The analysis of these operations uses a potential function based on the number of nodes on trunks (paths of length two or three) in the workspace. The potential method shows that each operation incurs only a constant amount of extra work beyond the obvious comparisons, yielding the stated amortized bounds.
Historical Context
The 2–3 heap was proposed as an alternative to other meldable priority‑queue structures such as the binomial heap and the Fibonacci heap. Its design seeks a balance between the simplicity of binary heaps and the more intricate restructuring of Fibonacci heaps, while retaining comparable asymptotic performance.
References
- Tadao Takaoka, “Theory of 2–3 Heaps,” 1999.
- Wikipedia article “2–3 heap,” which summarises the structure, operations, and analysis.
