in DS edited by
8,593 views
24 votes
24 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\}$

  1. $\left\{14,13,12,10, 8\right\}$
  2. $\left\{14,12,13,8,10\right\}$
  3. $\left\{14,13,8,12,10\right\}$
  4. $\left\{14,13,12,8,10\right\}$
in DS edited by
8.6k views

3 Answers

35 votes
35 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$
edited by
by
11 votes
11 votes

Answer is  :  [D] {14,13,12,,8,10}

edited by

1 comment

Thnx
0
0
3 votes
3 votes

option d

Answer:

Related questions