The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.3k 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\}$
asked in DS by Veteran (97.7k points)
edited by | 1.3k views

3 Answers

+24 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$
answered by Veteran (414k points)
edited by
+6 votes

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

answered by Loyal (7.9k points)
edited by
0 votes

option d

answered by Boss (34.2k 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
49,814 questions
54,522 answers
188,364 comments
75,385 users