Heap Sort
Before understanding Heap Sort and Heapify, we have to understand some basic concepts that will be used in further explanation like how to represent any given Binary Search Tree in form of an array, the difference between Full BST and complete BST, how to insert and delete elements from a heap, etc. Let’s start by understanding how to represent a Binary Search Tree in form of an Array.
1) Array Representation of BST
Start filling the elements in the array in a top to bottom and left to right fashion.
Let us understand this with help of an example. Following is the Binary Search Tree. I have taken alphabets for better and clear understanding.
(A)
/ \
B C
/\ / \
(D) (E) (F) (G)
This can be represented in an array as [A, B, C, D, E, F, G]
For a node at index [i], its parent is at [(i-1)/2] index. Its left child is at [(2*i)+1] index and its right child is at [(2*i)+2] index. Please note that indexing is done starting from zero till n-1.
2) Full and Complete Binary Tree
In a Full Binary Tree, all nodes have either 0 or two children. The above example is of a full binary tree.
In a Complete Binary Tree, all the levels are completely filled except the last level and the last level has all keys as left as possible.
Heap is a Complete Binary Tree.
3) Min Heap and Max Heap
Min Heap is a heap in which all the child nodes are either greater than or equal to the parent node. Below is an example.
(5)
/ \
(10) (20)
/ \ / \
(30) (40) (25) (50)
Array Representation: [5,10,20,30,40,25,50]
Max Heap is a heap in which all the child nodes are either less than or equal to the parent node. Below is an example.
(50)
/ \
(40) (35)
/ \ / \
(30) (20) (10) (15)
Array Representation: [50,40,35,30,20,10,15]
4) Insertion in a Heap
Note: Insertion in a heap is always done at the bottom of the heap(At the end of the array) and we then move the element to its correct position
Suppose we want to insert an element 63 in the above max heap example.
Step 1: Add the element to the end of the heap. Always add the elements at the leftmost available node.
(50)
/ \
(40) (35)
/ \ / \
(30) (20) (10) (15)
/
(63)
Array Representation: [50,40,35,30,20,10,15,63]
Step 2:
· Compare it to its parent element. If the child node is smaller than the parent node, swap the two nodes. Here, compare 63 and 30. As 63>30, we swap their places.
(50)
/ \
(40) (35)
/ \ / \
(63) (20) (10) (15)
/
(30)
Array Representation: [50,40,35,63,20,10,15,30]
· Now again, we compare 63 and 40. Since 63>40, we swap places. Now compare 63 and 50. Since 63>50, we swap again. The insertion is completed as there is no element above 63 less than itself and no number below it smaller than 63.
(50)
/ \
(63) (35)
/ \ / \
(40) (20) (10) (15)
/
(30)
Array Representation: [50,63,35,40,20,10,15,30]
(63)
/ \
(50) (35)
/ \ / \
(40) (20) (10) (15)
/
(30)
Array Representation: [63,50,35,40,20,10,15,30]
Time Complexity: O(Log n) It is due to the fact that a tree with n nodes has a height log n and an element may have to travel the height of the tree to find its correct position.
4) Deletion from a Heap ~ Heap Sort
Note: Deletion from a heap is always done from the top of the heap and we then move the last element in the heap(rightmost node) to take the topmost place and adjust the elements to form a min or max heap.
Suppose we want to delete elements from the below-given max heap.
(50)
/ \
(40) (35)
/ \ / \
(30) (20) (10) (15)
Array Representation: [50,40,35,30,20,10,15]
Step 1: Remove the topmost element and replace it with the rightmost node. This is done to maintain the complete binary tree property Here, we remove 50 and replace it with 15.
(15)
/ \
(40)______ (35)
/ \ /
(30) (20) (10)
Array Representation: [15,40,35,30,20,10, ]
Step 2: Since we have a blank space left at the end of the array, we add the removed element there. Note: The element is removed from the heap, but it is still there in the array.
We start comparing the current topmost element to its children. If it is smaller than one child, we swap their places. If it is smaller than both, we swap it with the greatest number of two children.
Here, 15<40 and 15< 35. Also, 40>30. So, we swap 15 and 40.
(40)
/ \
(15) (35)
/ \ /
(30) (20) (10)
Array Representation: [40,15,35,30,20,10|50]
Step 3: Again, we compare 15 to its children 30 and 20. 30 and 20>15 and 30>20 So, we swap 15 and 30.
(40)
/ \
(30) (35)
/ \ /
(15) (20) (10)
Array Representation: [40,30,35,15,20,10|50]
This is now a max heap with one element deleted.
Let's see what happens if we remove all the elements one by one.
· We remove 40, add it to the end of the array and replace it with 10.
(10)
/ \
(30) (35)
/ \
(15) (20)
Array Representation: [10,30,35,15,20|50,40]
· We adjust the heap to form a max heap.
10< 30 and 35 and 35>30. So, we swap 10 with 35.
(35)
/ \
(30) (10)
/ \
(15) (20)
Array Representation: [35,30,10,15,20|50,40]
· This is a max heap. We repeat this procedure for all the remaining elements as shown below.
(20)
/ \
(30) (10)
/
(15)
Array Representation: [20,30,10,15|50,40,35]
(30)
/ \
(20) (10)
/
(15)
Array Representation: [30,20,10,15|50,40,35]
This is a max heap. So, we remove 30. And replace it with 15.
(15)
/ \
(20) (10)
Array Representation: [15,20,10|50,40,35,30]
(20)
/ \
(15) (10)
Array Representation: [20,15,10|50,40,35,30]
This is a max heap. We remove 20 and replace it with 10.
(10)
|
(15)
Array Representation: [10,15|50,40,35,30,20]
(15)
|
(10)
This is a max heap. We remove 15 and replace it with 10.
(10)
Array Representation: [10|50,40,35,30,20,15]
Now, there is only one element in the array so, we can consider this as max heap and remove this element from the heap and add it to the end of the array. The heap is now empty and the array representation is given below.
Array Representation: [50,40,35,30,20,15,10]
We notice that the array representation gives us the elements of the heap in Sorted order. This is the concept used for heap sort. If we remove elements from Min Heap, we get the elements in ascending order.
Time Complexity: O(n*log n). Reason for this time complexity:
We need to remove all elements one by one i.e; n elements
And we need to adjust the tree each time which takes log n time as explained in the insertion of elements in a heap part.
Therefore, time complexity=O(n*log n)
