The Gateway to Computer Science Excellence
+15 votes
1.5k 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 by Veteran (105k points)
edited by | 1.5k views

3 Answers

+27 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$
by Veteran (431k points)
edited by
+7 votes

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

by Loyal (8.1k points)
edited by
0
Thnx
+1 vote

option d

by Boss (36.5k points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,229 comments
104,909 users