We have a binary heap on n elements and wish to insert n more elements (not…
2008
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
- A.
θ(logn)
- B.
θ(n)
- C.
θ(nlogn)
- D.
θ(n2)
Attempted by 450 students.
Show answer & explanation
Correct answer: B
Final answer: Θ(n)
Key idea: use the linear-time bottom-up heap construction (build-heap) on the combined array of elements.
Step 1: Put the n new elements at the end of the heap's array (now there are 2n elements).
Step 2: Run bottom-up heap construction: for each internal node from floor(2n/2) down to 1, perform sift-down to restore the heap property.
Why Θ(n): bottom-up heapify does amortized constant work per element. The total work equals the sum of work at each node (proportional to its height), which sums to O(number of elements). Therefore heapify on 2n elements takes Θ(2n)=Θ(n).
Alternative (slower) method: inserting the n elements one-by-one using the insert operation costs Θ(log n) each, giving Θ(n log n) total; this is valid but not optimal.