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 N_{max} is N_{max } = (2^{H+1} -1) .Minimum number of nodes in a Binary Heap of Height H, denoted by N_{min} is N_{min} = 2^{H }

^{#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.

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 (2^{h+1} – 1) nodes, the sum of heights of all the nodes is 2^{h+1} – 1 – (h+1)

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

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

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 !! **