Analysis of forming a heap from two sub-heaps
l3-way rounds are
played from the parent downward to the
leaves
lOnly one path toward the leaves is followed, since other sub-trees along the path donŐt change
lA 3-way round uses O(1) steps (2 comparisons, possible exchange)
lThe time to form a heap at level k from the leaves is therefore O(k).
lOnly one path toward the leaves is followed, since other sub-trees along the path donŐt change
lA 3-way round uses O(1) steps (2 comparisons, possible exchange)
lThe time to form a heap at level k from the leaves is therefore O(k).
lIn the worst case,
this is O(log(n)).