Question

Suppose we have a heap containing n = 2^k elements in an array of size ‘n’, and suppose that we repeatedly extract the minimum element, ‘n’ times, never performing insertions. To make the heap space efficient, we move the heap over to an array of size 2^j whenever an extraction decreases the number of elements to 2^j for any integer j. Suppose that the cost of each such move is Θ(2^j). What is the total movement cost caused by ‘n’ extract-mins starting from the heap of n elements? (Ignore the Θ(n log n) cost from the heapify operations themselves.

1.   Θ(n)
2.   Θ(2ⁿ)
3.   Θ(logn)
4.   Θ(nlogn)

Comments

could'nt understand this question...

---

answer A ?

---

yes..can u explain this question..?

Answer 1

• Heap is constructed using array.
• Initial Size of the array was $n = 2^{k}$
• because of extraction of minimum and never insertion, whenever size drops to $2^{k-1}$ we transfer the current heap elements to a new array of size $ n_1 = 2^{k-1}$ de-allocating that $n$ element array. Here $n_1 < n$
• Similarly whenever size drops to $2^{k-2}$ we transfer current elements to a new array of size $ n_2 = 2^{k-2}$ de-allocating that $n_1$ element array. Here $n_2 < n_1$.

$$\begin{align*} & \text{1st movement cost } &=2^{k-1} \\ & \text{2nd movement cost } &=2^{k-2} \\ & \text{3rd movement cost } &=2^{k-3} \\ & ----------- \\ & \text{last movement cost } &=2^{k-k} \\ & \text{Net movement cost } \frac{1*\left ( 2^{k}-1 \right )}{2-1} = \Theta(n) \\ \end{align*}$$ 

Comments

initially, it must be stored in $2^k$ size array, from that point extraction starts. So the first movement starts when no of elements reduces to $2^{k-1}$

---

consider n  = 16.

• After extraction starts no of elements reduces to 15,14,......9...8..and then we move elements to $2^3$ size array.

---

alright,we have to take in powers of 2 only..thats why..right??

so j can be any value between 0 to k-1

Answer 2

Ok, Let first move occur when elements equivalent to 2^(k-1)

Second move  occur when left elements equivalent to 2^(k - 2)

Any jth move will occur when left  elements equivalent to 2^(k - j)

Hence total number of moves will be k , and

and cost of jth move at any time will be 2^j

total cost :  2^0 + 2^1 + 2^2 ..... 2 ^ (k -1 )  =  2^k - 1  

which is almost N  (  N = 2^k )    

Hence theta(N)  complexity  , correct answer will be A.