GATE CS 2023 Q36 — Binary Heaps

A max-heap containing $n$ elements is represented as a nearly complete binary tree of height $h = \Theta(\log n)$.

Let's analyze the worst-case time complexity of both operations:

1. $\text{INSERT}(A, key)$:
   • To insert a new element, we place it at the next available leaf position (at the end of the array representation) to maintain the structural property of the complete binary tree.
   • We then perform a heapify-up (or bubble-up) operation to restore the max-heap property by comparing and swapping the element with its parent.
   • In the worst case, the newly inserted element travels from the leaf level to the root. The maximum number of swaps is proportional to the height of the tree, which is $O(\log n)$.
2. $\text{EXTRACT-MAX}(A)$:
   • The maximum element is always at the root of the max-heap, which can be accessed in $O(1)$ time.
   • To delete this element, we replace the root with the last element of the heap and decrease the heap size by 1.
   • We then perform a heapify-down (or bubble-down) operation from the root to restore the max-heap property by swapping the element with its larger child.
   • In the worst case, this element travels from the root down to a leaf. The maximum number of swaps is proportional to the height of the tree, which is $O(\log n)$.

Therefore, both $\text{EXTRACT-MAX}(A)$ and $\text{INSERT}(A, key)$ run in $O(\log n)$ time in the worst case.