Based on the binary heap data structure, heap sort is mainly considered as a comparison-based sorting algorithm. In this sorting technique, at first, the minimum element is found out and then the minimum element gets placed at its right position at the beginning of the array. For the rest of the elements, the same process gets repeated. So, we can say that heap sort is quite similar to the selection sort technique.
What Is Binary Heap?
Before exploring what Binary Heap refers to, lets first understand what is complete binary tree.
A complete binary tree is a type of binary tree in which every level is filled except possibly the last level and at the last level the nodes are filled from as far left as possible.
From this, we can conclude that a binary heap is a type of a complete binary tree in which the elements are stored in a special manner or in a special order such that the value stored in the parent node must be greater than or lesser than the values of the two children nodes.
The binary heap in which the parent node value is greater than its children node is called max heap and the binary heap in which the parent node value is lesser than the children node valuesis called min-heap.
Relationship Between Array Indexes and Tree Elements
A Binary Tree can be easily represented by the array and representing an array is very much space-efficient.
Now let us consider that the parent node has an index I in the array, then the left child node will have an index of 2*I+1, and the right child node will have an index of 2*I+2 in the array representation (This indexing follows zero-based indexing rule).
So, we can say that heap is basically considered as a tree based data structure and the tree is mainly a complete binary tree. If a complete binary tree has n number of nodes, then we can say that the height of the binary tree will be log n. For removing the higher priority or the lower priority element, this data structure is very useful.
Heap Data Structure/Types of Heap
- Min-Heap: The key present at the root node is smaller than or equal to keys of all the nodes present in the children nodes. And this same rule is recursively followed by all the subtrees of the binary tree.
- Max-Heap: In this data structure, the key which is present at the root node is greater than or equal to the keys of all the children nodes of the tree. The same property is recursively applicable for all the subtrees of the tree. The maximum key is present at the root of the tree for a Max-Heap.
Now let us go through the difference between the Min-Heap and the Max-Heap.
Difference Between Min-Heap and Max-Heap
Min Heap |
Max Heap |
|
The key which is present at the root node of the tree is lesser than or equal to the keys present at the children nodes. |
The key which is present at the root node of the tree is greater than or equal to the keys present at the children nodes. |
|
The minimum key element is present at the root in a Min-Heap. |
The maximum key element is present at the root in a Max-Heap |
|
Min-Heap uses the ascending property. |
Max-Heap uses the descending property. |
|
The smallest element has the priority in the construction of a Min-Heap. |
The largest element has the priority in the construction of a Max-Heap. |
|
The smallest element is the first element to be popped from the heap. |
The largest element is the first element to be popped from the heap. |
Now let us learn what heapify means.
What Is Heapify?
The process in which the binary tree is reshaped into a Heap data structure is known as Heapify. There are two child nodes at max in a binary tree. The heapify process can only be applied to that node whose children nodes are heapified.
A heap must be a complete binary tree. By applying a function called “heapify” to all the non-leaf elements of the heap, it can be converted to a Max-Heap after starting from a complete binary tree. Recursion is used by the Heapify algorithm.
Algorithm
heapify(array)
root = array[0]
largest = largest( array[0] , array [2 * 0 + 1]. array[2 * 0 + 2])
if(root != largest)
Swap(root, largest)
Example of Heapify:
20(0)
/ \
50(1) 40(2)
Child (50(1)) is greater than or equal the parent (20(0))
Swap Child node (50(1)) with the parent node (20(0))
70(0)
/ \
20(1) 40(2)
Let us now discuss heapify through different scenarios:
In Scenario-1 above, as we can see the root itself is the largest element, so there is no need for doing anything else.
In Scenario-2, the larger value is contained by the children node, so we need to swap the values for maintaining the property of max-heap. If we are familiar with recursion, then we must know that it is the base case.
Below image is an example where we have more than one level.
As we can see in the above image, the root or the parent node does not have the max-heap element, but in all the children subtrees the max-heap property has been maintained. So, in this case, until 2 reaches its actual position, we need to keep pushing 2 downwards.
So, for applying the max-heap property on such a tree in which the child subtrees are maintaining the max-heap property, we have to apply the heapify on the root again and again until the root node becomes larger than all the other nodes or becomes the leaf node.
Both these conditions can be applied in one heapify function.
The function given below will work for tree of any size and it will work for both the base cases. Using the below function, we can make tree Max-Heap by moving the tree to its correct position as long as the subtrees follow the max-heap property.
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
Working of Heap Sort
Now let us discuss the working of heap sort:
- The tree needs to be sliced in such a way that it follows the max-heap property and the largest element comes to the top root node of the tree.
- Next, we need to swap, which means that the root element needs to be removed and put at the end nth position of the array and the last item of the tree (heap) needs to be put at the vacant place of the tree.
- The size of the head should be reduced by 1.
- Then we need to Heapify the root element again so that the highest element is always on the top.
- The process gets repeated until all the items of the list get sorted.
Below gives code provides a clearer picture of the functioning of Heap Sort:
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// We need to apply heapify for getting the highest element at the root
heapify(arr, i, 0);
}
Understanding the Algorithm
Now let’s understand the heap sort algorithm with example.
- First we will ask the user to enter an array that is required to be sorted.
- Once the array is received, we need to create a heap for sorting the elements in ascending order.
- Now out of the heap, a max heap is needed to be created. Remember, the value of the root node/parent node is always greater than or equal to the value of the children nodes.
- After building the tree, the above condition must be checked. If the value of the child node is greater than the child node, we need to swap the values and repeat the process until it satisfies the max-heap property.
- Once all the conditions are satisfied, the root node needs to be swapped with the last node.
- As it is now sorted, we can remove the last node from our heap.
- The previous three steps (Steps 4,5,& 6) need to be repeated until there is only one element left in the heap.
Example array: [5,6,11,4,14,12,2]
We can go through the diagram given below for understanding the algorithm.
Implementing Heap Sort in C
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
void heapSort(int arr[], int n) {
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
}
//for printing the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main() {
int arr[] = {5,6,11,4,14,12,2};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is given in the following way \n");
printArray(arr, n);
}
Applications of Heap Sort
For systems like Linux Kernel which are concerned with security and such embedded systems, Heap Sort can be used.
This technique also helps in finding out the smallest or the largest element instantly from a data structure. Also, we can use Heap Sort to find the order in statistics and also to deal with the priority queues in prim’s algorithm.
Even though Heap Sort has a worst-case time complexity of O(nlogn) as compared to the other sorting algorithms like merge sort, quick sort, etc., its applications are minimal.
Heap Sort Time and Space Complexity
Time Complexity:
|
Best Case |
O(nlogn) |
|
Worst Case |
O(nlogn) |
|
Average Case |
O(nlogn) |
Space complexity is O(1).
Advantages and Disadvantages of Heap Sort
Advantages:
- The performance of Heap sort is very optimal and efficient which basically implies that no other sorting algorithm can perform better than this algorithm in comparison.
- Apart from what is necessary for holding the initial list of items to be sorted, it needs no additional space to work. So we can say for Heap Sort, the memory usage is very minimal.
- In comparison with other efficient sorting algorithms, this Heap Sort algorithm is very easy to understand as advanced computer science concepts like recursion are not used by this sorting algorithm.
Disadvantages:
- It is an unstable sort and the relative order might be arranged by it.
- The constant factors are expensive in heap sort. Though both the Quick Sort and Heap Sort have the same complexity (O(nlogn)), partitioning is faster than maintaining the heap.
- If we are working with huge datasets, then Heap Sort is not preferable, whereas Merge Sort works as a charm for huge datasets.
Conclusion
The article discusses Heap Sort and its concepts in detail. We covered the relationship between array indexes and tree elements, heap data structure and types of heap. We saw what heapify is, applications of heap sort, and learner about time and space complexity in heap sort. We also learned the working and algorithm of heap sort along with how to implement the same.
If you want to learn about the concept of Heap Sort in C in detail, you must enroll in Simplilearn’s Full Stack Web Development course. If you are looking for a starter course in C and development field in general, you can explore Simplilearn’s SkillUp courses, which offers numerous free online courses to help with the basics of multiple programming languages and other domains, from data science and business analytics to software development, AI, and machine learning. You can take up any of these free courses to upgrade your skills and advance your career.