2–3 heap

Template:Technical Template:One source 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 and in the worst case.
• Decrease-key takes constant amortized time.
• Insertion takes constant amortized time and $O(\log (n))$ time in the worst case.

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 $𝐫$ (e.g. $\mathrm{𝟏}$ 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 $◃$ on trees $S,T$ such that $L=S◃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 $𝐫$. The tree ${𝐫}^i$ is defined in the following way:

${𝐫}^i={𝐫}^{i-1}◃{𝐫}^{i-1}◃\dots ◃{𝐫}^{i-1}$

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

An r-ary polynomial of trees is defined as $P={𝐚}_{k-1}{𝐫}^{k-1}+\dots +{𝐚}_1𝐫+{𝐚}_0$ where $0\le a_i\le r-1$. This polynomial notation for trees of $n$ nodes is unique. The tree ${𝐚}_i{𝐫}^i$ is an $a_i$ copy of ${𝐫}^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 ${𝐚}_i{𝐫}^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 ${𝐚}_i{𝐫}^i$ and $𝐚{\text{'}}_i{𝐫}^i$, the trees are reordered in the main trunk based on the keys in the root of trees. If $a_i+a{\text{'}}_i\ge r$ there will be a term of form $({𝐚}_i+𝐚{\text{'}}_i-𝐫){𝐫}^i$ and a carry tree ${𝐫}^{i+1}$. Otherwise, there is only a tree $({𝐚}_i+𝐚{\text{'}}_i){𝐫}^i$. The sum of two r-nomial queues are 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.

A delete operation of the minimum is done by finding the minimum in the root of a tree, say $T$ and deleting it. The resulting polynomial queue $Q$ is added back 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)=\{\begin{array}{cc}\text{a single node}& i=0\\ T_1(i-1)◃\dots ◃T_s(i-1)& i\ge 1\text{ and }l\le s\le r\end{array}$

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$

.

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

When keys are assigned to 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$

.

Labelled (2,3) tree with workspaces of node 13 (yellow) and node 22 (blue) along with dimensions of nodes in pink

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

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. Since $0\le a_k\le r-1=2$ in the extended polynomial, there might be a need to adjust for the carry on trees that can occur from the insertion. If a tree $T(i)$ is being inserted into a tree ${𝐚}_{i}T(i)$ at the top level, there are three cases, depending on the value of ${𝐚}_i$.

1. ${𝐚}_i=0$: there is no tree $T(i)$ already in the heap, so we it is inserted into the heap. The term $T(i)$ is added to our extended polynomial.
2. ${𝐚}_i=1$: Form a new tree $\mathrm{𝟐}T(i)$ by joining the two trees using one comparison to maintain the heap ordering property of the labels.
3. ${𝐚}_i=2$: A carry of $T(i+1)$ is made with two comparisons. Another round of inserting is done with this carry tree on ${𝐚}_{i+1}T(i+1)$ in the heap.

Delete-min: First find the minimum by scanning the roots of the trees. Let ${𝐚}_{i}T(i)$ be the tree containing minimum element. Since this tree exists, this means ${𝐚}_i$ was $\mathrm{𝟏}$ or $\mathrm{𝟐}$. Deleting the root of this tree means removing the root of the linear chain ${𝐚}_i$ connecting copies of $T(i)$. The other copies of $T(i)$ give a tree of the form ${𝐛}_{i}T(i)$ where ${𝐛}_i=0$ if ${𝐚}_i=1$ or ${𝐛}_i=1$ if ${𝐚}_i=2$.

The root that was deleted was also the root of the first copy of $T(i)$, giving 2 or 3 $T(i-1)$ trees. Following this pattern, we end up with the collection of trees

${𝐛}_{j}T(0),{𝐛}_{j}T(1),\dots ,{𝐛}_{j}T(i)$

where ${𝐛}_j$ is $\mathrm{𝟏}$ or $\mathrm{𝟐}$ for $j=0,\dots ,i-1$ and ${𝐛}_{𝐢}$ as specified above.

This collection forms a heap $Q$ with can then be merged back with $P-{𝐚}_{i}T(i)$ to make sure only the minimum node was removed from the heap. (The merging operation is done through multiple insertions, each taking at most 3 comparisons).

Removal of a Tree: Trees rooted at the top most trunks of the heap are not removed. To remove the tree $tree(v)$ of type $T(i-1)$ of a node $v$, there are 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, 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 the 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 and no tree removal is required. However, the trunks on the top most trunk $i$ may need to be rearranged.

Analysis of Operations

Let the potential of a trunk consisting of three nodes be 3, and the potential of a trunk consisting of two nodes be 1. Define the function $S$ to be the sum of the potentials of all trunks, and let $\varphi =-S$. The actual cost will be the number of comparisons performed during the operation. Note that the potential of an empty heap is 0.

Decrease Key The number of nodes on trunks can increase or decrease during the removal of a tree, depending on the size of the workspace. The change in potential and number of comparisons can be observed in each case, which allows for a computation of the amortized cost.

Let the trunks in the cases going left-down be the $i$th dimension on which one of them $v$ stands. The trunks going right-down are the $i+1$th dimension. The $i$th trunks are ordered by non-decreasing length, although they are ordered by the labels of their head nodes in practice.

Cases of removal in different workspace sizes. Before removal (left) and after (right). Green nodes are possible options for removal.

In cases where $w=9,8,5$ and case 1 of $w=7$, no comparisons are needed because of the heap property and $\mathrm{\Delta }\varphi =-\mathrm{\Delta }S=-(-2)$. The amortized cost in these cases is then $\widehat{c_i}=0+\mathrm{\Delta }\varphi =2$.

In case 1 of $w=7$ and both cases of $w=6$, at most 1 comparison is needed and $\mathrm{\Delta }S$ decreases by 1, making the amortized cost 1.

In the final case where $w=4$, at most one comparison is done and $\mathrm{\Delta }S$ increases by 1, which gives an amortized cost of 0. The loss of the $i+1$th trunk will need to be fixed using the higher workspace of the node before it got removed from the trunk. The fixing process ends in one of the earlier cases or if no higher trunk exists. Since the amortized cost is non-negative and only one of the cases with positive amortized is done in this process, the overall amortized cost is still constant.

Insert When inserting a single node into an existing ${𝐚}_{0}T(0)$ in the tree, there are either 2 comparisons and $\mathrm{\Delta }S=2$ if ${𝐚}_0=2$ or there is one comparison with $\mathrm{\Delta }S=1$. Therefore the amortized cost is 0 throughout the initial insertion and the carry overs. The actual worst case time is $O(\log n)$ due to the carry overs and constant number of comparisons each time.

Delete Min It takes $O(\log n)$ time to find the minimum element, and also $O(\log n)$ to break apart the smaller subtrees, since there are at most $O(\log n)$ of them. To merge the subtrees, $O(\log n)$ insertions are done which take a constant amortized time each. The amortized time is then $O(\log n)$ and so is the worst case time.