GATE2009-60

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

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

edited
0
Thnx
1 vote

option d

Related questions

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\}$
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$
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$ ...
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$