Register

GATE CSE 2009 | Question: 59

• retagged by
13,853 views
23 votes
23 votes

Consider a binary max-heap implemented using an array.
Which one of the following array represents a binary max-heap?

  1. $\left\{25,12,16,13,10,8,14\right\}$    
  2. $\left\{25,14,13,16,10,8,12\right\}$
  3. $\left\{25,14,16,13,10,8,12\right\}$
  4. $\left\{25,14,12,13,10,8,16\right\}$
• retagged by
User Avatar

3 Answers

Best answer
15 votes
15 votes

Answer : (C)

The binary max-Heap looks like this :

Max-heap

 

• edited by
User Avatar
18 votes
18 votes
Taking the given array as level order traversal, we can build binary tree.

(A)  13 comes as child of 12, which is not allowed in a binary max-heap

(B) 16 comes as child of 14 violating max-heap property

(C) is a valid binary max-heap as all children are smaller than their parent

(D) 16 comes as child of 12, violating max-heap property
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

24 votes
24 votes
3 answers
1
go_editor asked Apr 23, 2016
8,729 views
GATE CSE 2009 | Question: 60
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\}$ $\left\{14,13,12,10, 8\right\}$ $\left\{14,12,13,8,10\right\}$ $\left\{14,13,8,12,10\right\}$ $\left\{14,13,12,8,10\right\}$
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\}$$\left\{14,13,12...
User Avatar
40 votes
40 votes
5 answers
2
Kathleen asked Sep 22, 2014
43,538 views
GATE CSE 2009 | Question: 37,ISRO-DEC2017-55
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$
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$
User Avatar
32 votes
32 votes
2 answers
3
Kathleen asked Sep 22, 2014
7,325 views
GATE CSE 2009 | Question: 36
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$ ...
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...
User Avatar
Link Copied!