Editing 2–3 heap (section)

== (2,3)-heap ==
Source:<ref name=":0" />

An <math>(l,r)-</math> tree <math>T(i)</math> is defined recursively by

<math> 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.</math>

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

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

An extended polynomial of trees, <math>P</math>, is defined by <math>P = a_{k-1}T(k-1) + \dots + a_1T(1) + a_0</math>. [[File:2 3 heaps eg.svg|thumb|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 <math>(l, r)-heap</math>, and the special case of <math>l = 2</math> and <math>r = 3</math> is a <math>(2, 3)-heap</math>. [[File:2 3 workspace eg.svg|frame|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 <math>v</math> is the local neighborhood, defined for nodes not on the main trunks of trees in the heap. Assume the dimension of <math>v</math> is <math>i - 1</math>, so that it is on an <math>i</math>th trunk. The workspace of <math>v</math> then consists of all the nodes on the <math>i</math>th trunk, the <math>i + 1</math>th trunk, and those on other <math>i</math>th trunks whose head nodes are on the <math>i + 1</math>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 <math>i + 1</math>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, <math>T(0)</math> labeled with this key. Since <math>0 \leq a_{k} \leq r - 1 = 2</math> 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 <math>T(i)</math> is being inserted into a tree <math>\mathbf{a}_i T(i)</math> at the top level, there are three cases, depending on the value of <math>\mathbf{a}_i</math>.

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

'''Delete-min''': First find the minimum by scanning the roots of the trees. Let <math>\mathbf{a}_iT(i)</math> be the tree containing minimum element. Since this tree exists, this means <math>\mathbf{a}_i</math> was <math>\mathbf{1}</math> or <math>\mathbf{2}</math>. Deleting the root of this tree means removing the root of the linear chain <math>\mathbf{a}_i</math> connecting copies of <math>T(i)</math>. The other copies of <math>T(i)</math> give a tree of the form <math>\mathbf{b}_iT(i)</math> where <math>\mathbf{b}_i = 0</math> if <math>\mathbf{a}_i = 1</math> or <math>\mathbf{b}_i = 1</math> if <math>\mathbf{a}_i = 2</math>.

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

<math>\mathbf{b}_jT(0), \mathbf{b}_jT(1), \dots, \mathbf{b}_jT(i)</math> 

where <math>\mathbf{b}_j</math> is <math>\mathbf{1}</math> or <math>\mathbf{2}</math> for <math>j = 0, \dots, i -1</math> and <math>\mathbf{b_i}</math> as specified above.

This collection forms a heap <math>Q</math> with can then be merged back with <math>P - \mathbf{a}_iT(i)</math> 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 <math>tree(v)</math> of type <math>T(i - 1)</math> of a node <math>v</math>, there are two cases, one where the workspace of <math>v</math> is of size 4, and another where the size is larger. Note that <math>v</math> is a node on an <math>i</math>th trunk of the heap.

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

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

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

'''Decrease Key''': Assume the key of node <math>v</math> of dimension <math>i - 1</math> is decreased, and it is not at the top level. Then <math>tree(v)</math> is removed and inserted into the <math>j</math>th term at the top level of the heap (i.e. <math>T(j)</math> in the extended polynomial), where <math>j = dim(v)</math>. If <math>v</math> 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 <math>i</math> may need to be rearranged.

=== Analysis of Operations ===

The [[Potential_method|potential method]] can be used to analyze the amortized time to perform 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 <math>S</math> to be the sum of the potentials of all trunks, and let <math>\phi = -S</math>. 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 <math>i</math>th dimension on which one of them <math>v</math> stands. The trunks going right-down are the <math>i + 1</math>th dimension. The <math>i</math>th trunks are ordered by non-decreasing length, although they are ordered by the labels of their head nodes in practice. 
[[File:2 3 heaps workspace cases.svg|thumb|500px|Cases of removal in different workspace sizes. Before removal (left) and after (right). Green nodes are possible options for removal.]]

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

In case 1 of <math>w = 7</math> and both cases of <math>w = 6</math>, at most 1 comparison is needed and <math>\Delta S</math> decreases by 1, making the amortized cost 1.

In the final case where <math>w = 4</math>, at most one comparison is done and <math>\Delta S </math> increases by 1, which gives an amortized cost of 0. The loss of the <math>i + 1</math>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 <math>\mathbf{a}_0 T(0)</math> in the tree, there are either 2 comparisons and <math>\Delta S = 2</math> if <math>\mathbf{a}_0 = 2</math> or there is one comparison with <math>\Delta S = 1</math>. Therefore the amortized cost is 0 throughout the initial insertion and the carry overs. The actual worst case time is <math>O(\log n)</math> due to the carry overs and constant number of comparisons each time.

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