Tips to solve Heap sort problems

 

Heap sort is an important topic from GATE 2017 perspective since Data Structures and Algorithms section carry high weight age in GATE CS.

We have been receiving e-mails from our readers as to assist them in preparing questions on Heap sort. Consequently, Prep ladder has devised this article which will share the tips and tricks for solving questions based on Heap sort.

 

Property of Heap Sort

Heap is basically a binary tree where all levels except the last/lowest level are full. So binary heap is complete binary and simple array can be used to implement them.

Min Heap - >  “ The father is <= children “

Max Heap ->  “The father is >= children “

 

must read : Expected cut-off of GATE 2017 with topic wise analysis of previous papers

 

4 Tips to Prepare Heap Sort for GATE CS 2017

 #Tip1

  Maximum number of nodes in a Binary Heap of Height H, denoted by Nmax is Nmax  = (2H+1 -1) .Minimum number of nodes in a Binary Heap of Height H, denoted by Nmin is Nmin = 2H

#Tip2

In a MaxHeap, the element with the largest priority becomes the root node while the element with the lowest priority is in the leaf node.In a MinHeap, the element with the lowest priority is the root while the element with the highest priority is in the leaf node. The changes are required only in path from the root to leaf or viceversa.

FREE Daily Quiz on Computers for
GATE-2017 Preparation
 
FREE Daily Quiz on Computers for GATE-2017 Preparation.
Start Quiz  

#Tip3

Let N be the number of nodes in the Heap. The worst-case complexity of Insert operation into a MaxHeap is O(log N) .In the DeleteMax operation, the running time in the worst case is O(log N)

#Tip4

Build Heap: A heap can be built in linear time from an arbitrarily sorted array. Running Time Analysis of Build Heap: To bound the running time, we should compute the sum of heights of all nodes = h1+h2+ h3+h4

            For a perfect Binary tree of Height h containing (2h+1 – 1) nodes, the sum of heights of all the nodes is 2h+1 – 1 – (h+1)

                  2h+1 – 1 – (h+1) =>   n – 1 – (logn +1) =>  O(n)

 

Therefore, the running time analysis of Build Heap is O(n).

 

FREE Daily Quiz on Computers for
GATE-2017 Preparation
 
FREE Daily Quiz on Computers for GATE-2017 Preparation.
Start Quiz  

Solved Examples From GATE

 

Question  :  The following elements are inserted one by one in the given order into a MaxHeap.

                32, 15, 20, 30, 12, 25, 16

                Which of the following is the resultant MaxHeap?

Answer :    (A)

Solution:  32, 15, 20, 30, 12, 25, 16

 

       1)  The resulting heap after insertion of 32, 15 and 20 is

       2) The heap after insertion of element 30,

       3) Since MaxHeap property is violated, therefore, 30 is swapped with 15

       4) The heap after insertion of element 12,

       5) The heap after insertion of element 25

       6) Since MaxHeap property is violated, therefore, 25 is swapped with 20

       7) The resulting heap after insertion of 16 is

                            

   We are hopeful that our tips would surely help the aspirants to excel in their preparation.

must read : 5 quick tips to solve questions on Normalization for GATE CS || Exam Preparation Simplified

 

Best Wishes !!

Search on PrepLadder