2–3 heap

In computer science, a 2–3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2–3 tree.

Time costs for some common heap operations are:

• Delete-min takes $O(\log(n))$ amortized time.
• Decrease-key takes constant amortized time.
• Insertion takes constant amortized time.

Polynomial of trees

Source:

A linear tree of size $r$ is a sequential path of $r$ nodes with the first node as a root of the tree and it is represented by a bold $\mathbf {r}$ (e.g. $\mathbf {1}$ is a linear tree of a single node). Product $P=ST$ of two trees $S$ and $T$, is a new tree with every node of $S$ is replaced by a copy of $T$ and for each edge of $S$ we connect the roots of the trees corresponding to the endpoints of the edge. Note that this definition of product is associative but not commutative. Sum $S+T$ of two trees $S$ and $T$ is the collection of two trees $S$ and $T$.

Consider the operation $\triangleleft$ on trees $S,T$ such that $L=S\triangleleft T$. The tree $L$ is produced by linking the root of the tree $T$ as a child of the root of tree $S$. Now consider the linear tree $\mathbf {r}$. We define $\mathbf {r} ^{i}$ in the following way:

$\mathbf {r} ^{i}=\mathbf {r} ^{i-1}\triangleleft \mathbf {r} ^{i-1}\triangleleft \dots \triangleleft \mathbf {r} ^{i-1}$

The path created from this linking forms the $i$th trunk of $\mathbf {r} ^{i}$ which can also be called the $i$th dimension of the tree.

An r-ary polynomial of trees is defined as $P=\mathbf {a} _{k-1}\mathbf {r} ^{k-1}+\dots +\mathbf {a} _{1}\mathbf {r} +\mathbf {a} _{0}$ where $0\leq a_{i}\leq r-1$. This polynomial notation for trees of $n$ nodes is unique. The tree $\mathbf {a} _{i}\mathbf {r} ^{i}$ is an $a_{i}$ copy of $\mathbf {r} ^{i}$ such that their roots are connected with $a_{i}-1$ edges sequentially. The path of these $a_{i}-1$ edges is called the main trunk of the tree $\mathbf {a} _{i}\mathbf {r} ^{i}$. Furthermore, an r-ary polynomial of trees is called an r-nomial queue if nodes of the polynomial of trees are associated with keys in heap property.

A polynomial heap, in fact a (2,3) heap with a dimension representation of its trees

Operations on r-nomial queues

To merge two terms of form $\mathbf {a} _{i}\mathbf {r} ^{i}$ and $\mathbf {a} '_{i}\mathbf {r} ^{i}$, we just reorder the trees in the main trunk based on the keys in the root of trees. If $a_{i}+a'_{i}\geq r$ we will have a term of form $(\mathbf {a} _{i}+\mathbf {a} '_{i}-\mathbf {r} )\mathbf {r} ^{i}$ and a carry tree $\mathbf {r} ^{i+1}$. Otherwise, we would have only a tree $(\mathbf {a} _{i}+\mathbf {a} '_{i})\mathbf {r} ^{i}$. So the sum of two r-nomial queues are actually similar to the addition of two number in base $r$.

An insertion of a key into a polynomial queue is like merging a single node with the label of the key into the existing r-nomial queue, taking $O(r\log _{r}{n})$ time.

To delete the minimum, first, we need to find the minimum in the root of a tree, say $T$, then we delete the minimum from $T$ and we add the resulting polynomial queue $Q$ to $P-T$ in total time $O(r\log _{r}{n})$.

(2,3)-heap

Source:

An $(l,r)-$ tree $T(i)$ is defined recursively by

$T(i)=\left\{{\begin{array}{cc}{\text{a single node}}&i=0\\T_{1}(i-1)\triangleleft \dots \triangleleft T_{s}(i-1)&i\geq 1{\text{ and }}l\leq s\leq r\end{array}}\right.$

The root of the tree $T(i)$ has degree $i$, and can be formed by different trees of degree $i-1$. The root of $T(i)$ is called the head node of the $i$th trunk. The dimension of non-head nodes on the trunk is $i-1$, while the dimension of the head node is $i$ or larger, depending on whether it gets linked again. The tree of type $T(i-1)$ on the $i$th trunk of $T(i)$ rooted at a node $v$ is called $tree(v)$.

Informally, a $(2,3)$ tree of dimension $d$ is formed by linking roots of 2 or 3 trees of dimension $d-1$ in a line.

An extended polynomial of trees, $P$, is defined by $P=a_{k-1}T(k-1)+\dots +a_{1}T(1)+a_{0}$. If we assign keys into the nodes of an extended polynomial of trees in heap order it is called an $(l,r)-heap$, and the special case of $l=2$ and $r=3$ is a $(2,3)-heap$.

An example of a 2-3 heap, where P = 2T(3) + 1T(2) + 1T(0)

Workspace of a Node The workspace of a node $v$ is the local neighborhood, defined for nodes not on the main trunks of trees in the heap. Assume the dimension of $v$ is $i-1$, so that it is on an $i$th trunk. The workspace of $v$ then consists of all the nodes on the $i$th trunk, the $i+1$th trunk, and those on other $i$th trunks whose head nodes are on the $i+1$th trunk. The workspace is then a collection of nodes between size 4 to 9. The head node of the workspace is the node on the first position of the $i+1$th trunk.

Operations on (2,3)-heap

Delete-min: First find the minimum by scanning the root of the trees. Let $T(i)$ be the tree containing minimum element and let $Q$ be the result of removing root from $T(i)$. Then merge $P-T(i)$ and $Q$ (The merge operation is similar to merge of two r-nomial queues).

Insertion: In order to insert a new key, merge the currently existing (2,3)-heap with a single node tree, $T(0)$ labeled with this key.

Removal of a Tree: Trees rooted at the top most trunks of the heap are not removed. If we want to remove the tree $tree(v)$ of type $T(i-1)$ of a node $v$, we need to consider two cases, one where the workspace of $v$ is of size 4, and another where the size is larger. Note that $v$ is a node on an $i$th trunk of the heap.

In a workspace of size larger than 4, the $i$th trunk either has 2 nodes or 3 nodes. If it has 3 nodes, then it can be of the form $(u,v,w)$ or $(u,w,v)$. In either case, we can remove $tree(v)$ and shrink the trunk. Note that $v$ cannot be the first node on the $i$th trunk since that node would be on the $i+1$th trunk, which must exist as nodes on the top most trunks are not removed.

If the $i$th trunk is of the form $(u,v)$, then remove $tree(v)$ and account for the loss of the $i$th trunk by moving around some other trees of type $T(i-1)$ in the workspace.

For the case in which the workspace is of size 4, remove $tree(v)$ and rearrange the other three nodes so that two come under the head node of the workspace. This makes an $i$th trunk of length two (three nodes in a line) but causes a loss of an $(i+1)$th trunk. This loss is fixed by moving around trees from workspace of nodes on the $(i+1)$th dimension. This process continues upwards in dimension until it is resolved.

Decrease Key: Assume the key of node $v$ of dimension $i-1$ is decreased, and it is not at the top level. Then $tree(v)$ is removed and inserted into the $j$th term at the top level of the heap (i.e. $T(j)$ in our extended polynomial), where $j=dim(v)$. If $v$ was at the top level of its tree, then the heap property was not violated from decrease key so no tree removal is required. However, the trunks on the top most trunk $i$ may need to be rearranged.