edited by
8,624 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\}$
edited by

3 Answers

Best answer
35 votes
35 votes
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
Answer:

Related questions

39 votes
39 votes
5 answers
1
Kathleen asked Sep 22, 2014
43,277 views
What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$.$2$$3$$4$$5$
32 votes
32 votes
2 answers
2
Kathleen asked Sep 22, 2014
7,256 views
The keys $12, 18, 13, 2, 3, 23, 5$ and $15$ are inserted into an initially empty hash table of length $10$ using open addressing with hash function $h(k) = k \mod 10$ and...
23 votes
23 votes
3 answers
3
Kathleen asked Sep 22, 2014
13,638 views
Consider a binary max-heap implemented using an array.Which one of the following array represents a binary max-heap?$\left\{25,12,16,13,10,8,14\right\}$ $\left\{25,14,...