edited by
13,939 views
20 votes
20 votes

A priority queue is implemented as a Max-Heap. Initially, it has $5$ elements. The level-order traversal of the heap is: $10, 8, 5, 3, 2$. Two new elements $1$ and $7$ are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is: 

  1. $10, 8, 7, 5, 3, 2, 1$
  2. $10, 8, 7, 2, 3, 1, 5$
  3. $10, 8, 7, 1, 2, 3, 5$
  4. $10, 8, 7, 3, 2, 1, 5$
edited by

1 Answer

Best answer
26 votes
26 votes

Answer is (D)

Whenever we insert an element in heap, it will be in last level from left to right. So, here we insert element $1$ and $7$ as children of node $5$. Then we perform heapify algorithm until we get the min/max heap. So, finally we get the heap whose level order traversal is $10,8,7,3,2,1,5$

Initial heap:

After insert of $1$

After insert of $7$

edited by
Answer:

Related questions

22 votes
22 votes
8 answers
1
Kathleen asked Sep 22, 2014
22,975 views
In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is:$nk$$(n-1)k + 1$$n(k-1) +1$$n(k-1)...
31 votes
31 votes
4 answers
2
Kathleen asked Sep 22, 2014
24,246 views
How many distinct binary search trees can be created out of $4$ distinct keys?$5$$14$$24$$42$
43 votes
43 votes
8 answers
3
Kathleen asked Sep 22, 2014
19,328 views
An Abstract Data Type (ADT) is:same as an abstract classa data type that cannot be instantiateda data type for which only the operations defined on it can be used, but no...
73 votes
73 votes
5 answers
4