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 “
4 Tips to Prepare Heap Sort for GATE CS 2017
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
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.
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)
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).
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.
Best Wishes !!