An Introduction To Heap Sort With Examples.
Heapsort is one of the most efficient sorting techniques. This technique builds a heap from the given unsorted array and then uses the heap again to sort the array.
Heapsort is a sorting technique based on comparison and uses binary heap.
=> Read Through The Easy C++ Training Series.
Table of Contents:
What Is A Binary Heap?
A binary heap is represented using a complete binary tree. A complete binary tree is a binary tree in which all the nodes at each level are completely filled except for the leaf nodes and the nodes are as far as left.
A binary heap or simply a heap is a complete binary tree where the items or nodes are stored in a way such that the root node is greater than its two child nodes. This is also called max heap.
The items in the binary heap can also be stored as min-heap wherein the root node is smaller than its two child nodes. We can represent a heap as a binary tree or an array.
While representing a heap as an array, assuming the index starts at 0, the root element is stored at 0. In general, if a parent node is at the position I, then the left child node is at the position (2*I + 1) and the right node is at (2*I +2).
General Algorithm
Given below is the general algorithm for heap sort technique.
- Build a max heap from the given data such that the root is the highest element of the heap.
- Remove the root i.e. the highest element from the heap and replace or swap it with the last element of the heap.
- Then adjust the max heap, so as to not to violate the max heap properties (heapify).
- The above step reduces the heap size by 1.
- Repeat the above three steps until the heap size is reduced to 1.
As shown in the general algorithm to sort the given dataset in increasing order, we first construct a max heap for the given data.
Let us take an example to construct a max heap with the following dataset.
6, 10, 2, 4, 1
We can construct a tree for this data set as follows.
In the above tree representation, the numbers in the brackets represent the respective positions in the array.
In order to construct a max heap of the above representation, we need to fulfill the heap condition that the parent node should be greater than its child nodes. In other words, we need to “heapify” the tree so as to convert it to max-heap.
After heapification of the above tree, we will get the max-heap as shown below.
As shown above, we have this max-heap generated from an array.
Next, we present an illustration of a heap sort. Having seen the construction of max-heap, we will skip the detailed steps to construct a max-heap and will directly show the max heap at each step.
Illustration
Consider the following array of elements. We need to sort this array using the heap sort technique.
Let us construct a max-heap as shown below for the array to be sorted.
Once the heap is constructed, we represent it in an Array form as shown below.
Now we compare the 1st node (root) with the last node and then swap them. Thus, as shown above, we swap 17 and 3 so that 17 is at the last position and 3 is in the first position.
Now we remove the node 17 from the heap and put it in the sorted array as shown in the shaded portion below.
Now we again construct a heap for the array elements. This time the heap size is reduced by 1 as we have deleted one element (17) from the heap.
The heap of the remaining elements is shown below.
In the next step, we will repeat the same steps.
We compare and swap the root element and last element in the heap.
After swapping, we delete the element 12 from the heap and shift it to the sorted array.
Once again we construct a max heap for the remaining elements as shown below.
Now we swap the root and the last element i.e. 9 and 3. After swapping, element 9 is deleted from the heap and put in a sorted array.
At this point, we have only three elements in the heap as shown below.
We swap 6 and 3 and delete the element 6 from the heap and add it to the sorted array.
Now we construct a heap of the remaining elements and then swap both with each other.
After swapping 4 and 3, we delete element 4 from the heap and add it to the sorted array. Now we have only one node remaining in the heap as shown below.
So now with only one node remaining, we delete it from the heap and add it to the sorted array.
Thus the above shown is the sorted array that we have obtained as a result of the heap sort.
In the above illustration, we have sorted the array in ascending order. If we have to sort the array in descending order then we need to follow the same steps but with the min-heap.
Heapsort algorithm is identical to selection sort in which we select the smallest element and place it into a sorted array. However, heap sort is faster than selection sort as far as the performance is concerned. We can put it as heapsort is an improved version of the selection sort.
Next, we will implement Heapsort in C++ and Java language.
Recommended Reading => Stack vs Heap – Know the Differences
The most important function in both the implementations is the function “heapify”. This function is called by the main heapsort routine to rearrange the subtree once a node is deleted or when max-heap is built.
When we have heapified the tree correctly, only then we will be able to get the correct elements in their proper positions and thus the array will be correctly sorted.
C++ Example
Following is the C++ code for heapsort implementation.
#include <iostream>
using namespace std;
// function to heapify the tree
void heapify(int arr[], int n, int root)
{
int largest = root; // root is the largest element
int l = 2*root + 1; // left = 2*root + 1
int r = 2*root + 2; // right = 2*root + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != root)
{
//swap root and largest
swap(arr[root], arr[largest]);
// Recursively heapify the sub-tree
heapify(arr, n, largest);
}
}
// implementing heap sort
void heapSort(int arr[], int n)
{
// build heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// extracting elements from heap one by one
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);
// again call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* print contents of array - utility function */
void displayArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// main program
int main()
{
int heap_arr[] = {4,17,3,12,9,6};
int n = sizeof(heap_arr)/sizeof(heap_arr[0]);
cout<<"Input array"<<endl;
displayArray(heap_arr,n);
heapSort(heap_arr, n);
cout << "Sorted array"<<endl;
displayArray(heap_arr, n);
}
Output:
Input array
4 17 3 12 9 6
Sorted array
3 4 6 9 12 17
Next, we will implement the heapsort in Java language
Java Example
// Java program to implement Heap Sort
class HeapSort
{
public void heap_sort(int arr[]) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// heapify the sub-tree
void heapify(int arr[], int n, int root)
{
int largest = root; // Initialize largest as root
int l = 2*root + 1; // left = 2*root + 1
int r = 2*root + 2; // right = 2*root + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != root) {
int swap = arr[root];
arr[root] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
//print array contents - utility function
static void displayArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
}
class Main{
// main program
public static void main(String args[])
{
int arr[] = {4,17,3,12,9,6};
int n = arr.length;
HeapSort ob = new HeapSort();
System.out.println("Input array: ");
HeapSort.displayArray(arr);
ob.heap_sort(arr);
System.out.println("Sorted array:");
HeapSort.displayArray(arr);
}
}
Output:
Input array:
4 17 3 12 9 6
Sorted array:
3 4 6 9 12 17
Conclusion
Heapsort is a comparison based sorting technique using binary heap.
It can be termed as an improvement over selection sort since both these sorting techniques work with similar logic of finding the largest or smallest element in the array repeatedly and then placing it into the sorted array.
Heap sort makes use of max-heap or min-heap to sort the array. The first step in heap sort is to build a min or max heap from the array data and then delete the root element recursively and heapify the heap until there is only one node present in the heap.
Heapsort is an efficient algorithm and it performs faster than selection sort. It may be used to sort an almost sorted array or find k largest or smallest elements in the array.
With this, we have completed our topic on sorting techniques in C++. From our next tutorial onwards, we will start with data structures one by one.
=> Look For The Entire C++ Training Series Here.