GATE CSE 2004 | Question: 37

Question

The elements $32, 15, 20, 30, 12, 25, 16,$ are inserted one by one in the given order into a maxHeap. The resultant maxHeap is

• A.  
• B.
• C.
• D.

Answer 1

The answer is option A.

Just keep inserting elements making sure resulting Tree is nearly Complete. (Heap Property) .

While inserting any node, if you find that  Value of New Node $>$ Value of its parent, bubble it up to keep Max heap property

Comments

Just to confirm TC would NLOGN right ??

---

Nikhil_v

Yes, n nodes are inserted and at the worst case we need to correct it till the root which is of height log n..
So, O(nlogn)

Answer 2

Insert each node as the left most leaf and check if it is less than the parent or not, if not then swap it with the parent

   32

   32
   /
15

   32
   /  \
15  20

Now 30 cannot be inserted as 15's child, so it will be in 15's place with 15 as it's child

    32
    /  \
 30  20
  /
15

     32
     /  \
  30  20
  /  \
15  12

25 cannot be inserted as 20's child, so it will be in place of 20, with 20 as it's child

        32
        /  \
     30   25
    /  \      /
 15  12  20

        32
        /   \
     30    25
    /  \      /  \
 15  12  20  16

Comments

ASNR1010

The first one is the correct approach as per previous GATE questions are concerned.

---

Hats off bro

---

@RavGopal We need heapify for each new element inserted. No need to wait for second children. When the new node comes attach according to the full binary tree then apply heapify . (As mentioned in the question The elements  are inserted one by one in the given order into a maxHeap.) 

Answer 3

Option a is correct just try to insert an element and shift whenever necessary Here shift operation is performed when 30 and 25 is inserted