The cost of keeping
the heap happy
lThe tournament path could be as long as the path from the root to a
leaf.
lAlong the path, a number of O(1) rounds were played.
lThe cost for one post-retirement adjustment is therefore O(log(n)).
lRetiring all n elements in sequence gives us the sorted order.
lOverall then, we have O(n log(n)) for Phase II.