search
Log In
17 votes
2.1k views

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
2.1k views

3 Answers

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$

edited by
10 votes

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


edited by
0
Thnx
1 vote

option d

Answer:

Related questions

15 votes
3 answers
1
2.3k 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,13,16,10,8,12\right\}$ $\left\{25,14,16,13,10,8,12\right\}$ $\left\{25,14,12,13,10,8,16\right\}$
asked Sep 22, 2014 in DS Kathleen 2.3k views
22 votes
4 answers
2
11.5k 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$
asked Sep 22, 2014 in DS Kathleen 11.5k views
22 votes
2 answers
3
1.9k 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$ ...
asked Sep 22, 2014 in DS Kathleen 1.9k views
29 votes
3 answers
4
3.9k views
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... is $\langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$
asked Apr 23, 2016 in Operating System jothee 3.9k views
...