Thnx

17 votes

Consider a binary max-heap implemented using an array.

What is the content of the array after two delete operations on $\left\{25,14,16,13,10,8,12\right\}$

- $\left\{14,13,12,10, 8\right\}$
- $\left\{14,12,13,8,10\right\}$
- $\left\{14,13,8,12,10\right\}$
- $\left\{14,13,12,8,10\right\}$

28 votes

Best answer

During delete, the root element is removed, replaced with the last element and heap property is corrected by pushing the root downwards. So, for first delete,

$25 \ 14 \ 16 \ 13 \ 10 \ 8 \ 12 \rightarrow 12 \ 14 \ 16 \ 13 \ 10 \ 8 \rightarrow 16 \ 14 \ 12 \ 13 \ 10 \ 8$ (the element not satisfying max-heap property is exchanged with the largest of its children) (heap property satisfied)

Second delete:

$16 \ 14 \ 12 \ 13 \ 10 \ 8 \rightarrow 8 \ 14 \ 12 \ 13 \ 10 \rightarrow 14 \ 8 \ 12 \ 13 \ 10 \rightarrow 14 \ 13 \ 12 \ 8 \ 10$ (heap property satisfied)

Correct Answer: $D$

$25 \ 14 \ 16 \ 13 \ 10 \ 8 \ 12 \rightarrow 12 \ 14 \ 16 \ 13 \ 10 \ 8 \rightarrow 16 \ 14 \ 12 \ 13 \ 10 \ 8$ (the element not satisfying max-heap property is exchanged with the largest of its children) (heap property satisfied)

Second delete:

$16 \ 14 \ 12 \ 13 \ 10 \ 8 \rightarrow 8 \ 14 \ 12 \ 13 \ 10 \rightarrow 14 \ 8 \ 12 \ 13 \ 10 \rightarrow 14 \ 13 \ 12 \ 8 \ 10$ (heap property satisfied)

Correct Answer: $D$