Operations

Report Min - O(1) Worst Case

Trivially, min is always at the Root

Decrease Key - O(1) Worst Case

To decrease the key of node x to v

1. If x is the root - DONE
2. If v is smaller than the root value, swap the two values
3. Cut the subtree rooted at x and link it to the root
4. Perform ≤ 1 Loss Reduction
5. Perform ≤ 6 Active Root Reduction and ≤ 4 Root Degree Reduction

• Trivially, all operations are O(1), and we perform a constant amount of actions for each step.
• Note, 3 Active Root Reduction + 2 Root Degree Reduction decreases both Root degree and Active Root numbers by 1. Since the violations could be broken by 2 at most(one from x and one from loss reduction), step 5 guarantees no violations afterward

Effects on Invariants

• I1: This is trivially true as linking to the root(passive) does not affect I1 at all and the transformations in step 4 and 5 do not cause this to be violated(as explained before)
• I2: Let y be the parent of x, if y and x are both active nodes, then the total loss will increase by 1 and may cause I3 to be violated by 1 (L = R + 2). However, by Lemma 3, we are guaranteed to be able to perform one loss reduction in step 4.
• I3: If both x and its original parent was active, the total number of active root may increase to R + 2. However, by Lemma 4, we are guaranteed to be able to perform the reductions in step 5.
• I4: The root degree increases by 1 after adding x. If this makes the root degree to be R + 4(violation), then by Lemma 5, we can perform the transformations in Step 5 to bring down the root degree (and active node number)
• I5: No non-root nodes get new nodes and no transformation will break this invariant.
• So, all 5 invariants are kept after decrease key

Merge - O(1) Worst Case

To merge H1 and H2, and w.l.o.g assume size(H1) ≤ Size(H2)

1. Make all nodes in H1 passive - This can be done in O(1) and will be shown in the next section
2. Link H1 and H2 such that the root with a smaller key becomes the new root
3. Set the new Q to be Q1 + larger Root of H1 and H2 + Q2 (note Qi is the Q for Hi)
4. Perform 0 or 1 Active Root Reduction and 0 or 1 Root Degree Reduction

• It's easy to see all steps are O(1)

Effects on Invariants

• I1: Trivially, no effects as no new active nodes are formed.
• I2: Trivially, no violation as the total loss will not increase (passive nodes no longer have loss) while R and N increased.
• I3: The number of active roots of the new heap is the number of active roots in the larger heap, since N (thus R) increases -- no violations
• I4: The root degree increases by 1 after the linking. If this makes the root degree to be R + 4, then from Lemma 5, we will perform the transformations in step 4
• I5: During the linking, one root node becomes a passive non-root node. However, it had at most R + 3 nodes before (by I4), and R + 3 <= 2 log(2N - p) + 9 for any p -- no violations

  All nodes in the smaller heap become passive, thus their degree constraints could go from + 10 to just +9. However, for the smaller heap, the new N is at least twice as big as before, and their position is unchanged in the new Q, thus the new constraint is actually increased by at least one -- no violations

  All nodes in the larger heap remain their active/passive status and have their p pushed back by k (i.e. k=size of the small heap) position, but N is also increased by the same size. So 2N - p actually increases and the constraints strengthened -- no violations

• So, all 5 invariants are kept after Merge

Insert - O(1) Worst Case

Assume we want to insert node x

1. Create one heap with a passive node x
2. Merge it with the main heap

• Since this is essentially just a Merge operation, no invariants are broken

DeleteMin - O(LogN) Worst Case

1. Scan through the children of the root and find node x with the minimum value
2. Make x passive
3. Link all the other children of the root to x.
4. Remove x from Q, delete the original root and make x the new root.
5. Do this twice: move the first node, y, in Q to the back. If y has two passive children, link both to the root.
6. Perform 0 or 1 Loss Reduction.
7. Perform O(LogN) numbers of Active root reduction and Root Degree Reduction until none is possible. (Note we need O(LogN) times because every 2 Active root reduction + 3 Root Degree Reduction reduces root degree by 1, and the new root degree increases by at most 2logN + 12 + 4(By I5 and there are ≤ 4 new nodes from step 5), and Active Roots increase by at most R(by Lemma 2, x had at most R active children)

• This is O(LogN) since all operations are O(1), but we need to perform the transformations O(LogN) times

Effects on Invariants