Editing 2–3 heap (section)

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