Question

Let \(A\) be a priority queue implemented using a max-heap. 
Extract-Max(A) deletes and returns the maximum element; 
Insert(A, key) inserts a new element. The max-heap property is preserved after each operation. 
When \(A\) has \(n\) elements, which statement about the worst-case running times is TRUE?

• A. Both Extract-Max(A) and Insert(A,key) run in \(O(1)\).
• B. Both Extract-Max(A) and Insert (A,key) run in \(O(\log n)\).
• C. Extract-Max(A) runs in \(O(1)\) whereas Insert(A,key) runs in \(O(n)\).
• D. Extract-Max}(A) runs in \(O(1)\) whereas Insert(A,key) runs in \(O(\log n)\).

Hint:

In heaps, the cost is proportional to the tree height. For binary heaps, height \(\sim \log_2 n\) \(\Rightarrow\) both sift-up and sift-down are \(O(\log n)\). To get \(O(1)\) amortized inserts, you’d need a different structure (e.g., Fibonacci heap), not a binary heap.

Answer 1

The Correct Option is B

Step 1: Structure of a max-heap. A binary heap is a complete binary tree stored in an array, with height \(\lfloor \log_2 n \rfloor\).
Step 2: Extract-Max(A). We remove the root (index \(1\)), move the last element to the root, and then heapify-down (sift-down) comparing with children and swapping along a path from root to a leaf in the worst case.
The path length is at most the heap height \(\Rightarrow\) time \(= O(\log n)\).
Step 3: Insert(A, key). We append the new key at the end (index \(n{+}1\)) and then heapify-up (sift-up) by swapping with the parent while the max-heap property is violated; this path can go from a leaf to the root.
The path length is at most the heap height \(\Rightarrow\) time \(= O(\log n)\).
Step 4: Eliminate other options. \(O(1)\) for either operation would require no percolation, which is not guaranteed in the worst case; \(O(n)\) for insertion is too pessimistic for binary heaps.
Final Answer: Worst-case: Extract-Max = \(O(\log n)\), Insert = \(O(\log n)\).