Up-Heapify

A bit simpler.

Look at node i (initially i=n).

• If $\mbox{key}[i] \ge \mbox{key}[\mbox{parent}[i]]$, all is well. (Why?)
• Similarly if i is the root. (Why?)
• Otherwise, swap i and its parent.
• Start again on the parent that changed (i.e., move i up).

We know that the only node that may violate the heap property is the new i. (Why?)

Kind of like bubblesort or insertion sort in a tree. The last leaf value trickles up until it stops.

Running Time? (Maximum number of comparisons and swaps.)