Editing 2–3 heap (section)

=== 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.