Heapsort is a sorting algorithm that uses Binary heaps for the purpose of sorting. Heaps can be of two types, min-heap and max heap.
Heapsort is an improved version of selection sort.
For this tutorial we will be using max heap for implementing Heapsort.
Max heap follows the property that the parent element is always greater than its children. That means in a max heap the root is always the maximum of all the elements. Heapsort uses this property to arrange elements in a sorted manner.
This tutorial assumes that you have a basic understanding of heaps. In case you want to learn about heaps, you can go over this tutorial on heaps and its implementation. (add link)
Algorithm
The algorithm for Heapsort is as follows :
- Build a max heap from the input array.
- Replace root (maximum) with the last item of the heap.
- Reduce the size of the heap by 1.
- Heapify the root of the tree by calling DownHeapify
- Repeat step 2 to 4 while the size of the heap is greater than 1.
At each iteration, we are taking the maximum element and placing it at the end of the heap. Then we are reducing the size of the heap. As we carry on this process, we are sorting the array from the end.
We will be calling the function downheapify( ) to make sure that the heap property is satisfied after reducing the size.
HeapSort Implementation
To heapify the array we use a recursive function that moves from the root towards the leaf nodes. This function at each node compares the parent to its children. If the value of parent node is less than its children nodes, it swaps the values. This swap makes sure that the max heap property is satisfied.
After performing the swap if further calls the downheapify function on the children.
This function needs to be called every time an element is added or deleted from the heap.
In a heap the position of children are given by :
|
1 2 |
Left child : (2*i) + 1 Right child : (2*i) + 2 |
The code for downheapify is as follows :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
static void downheapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; // finding the maximum of left and right if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; //swapping if child >parent if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; downheapify(arr, n, largest); } } |
To sort an array, we first need to create a heap out of it. This is done by the following lines of code :
|
1 2 |
for (int i = n / 2 - 1; i >= 0; i--) downheapify(arr, n, i); |
We only need to consider non-leaf nodes while calling downheapify, since leaf nodes already satisfy the heap property.
The next step is to extract an element from the root position and swap it with the last position of the heap. Once this is done, we reduce the size of the heap and again call downheapify. The lines of code that do this are :
|
1 2 3 4 5 6 7 8 9 |
for (int i=n-1; i>0; i--) { // swap the last element with root int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // i is the size of the reduced heap downheapify(arr, i, 0); } |
The complete code for sort function is :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public static void sort(int arr[]) { int n = arr.length; //build heap by calling heapify on non leaf elements for (int i = n / 2 - 1; i >= 0; i--) downheapify(arr, n, i); //extract elements from the root and call healpify for (int i=n-1; i>0; i--) { // swap the last element with root int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // i is the size of the reduced heap downheapify(arr, i, 0); } } |
Apart from these two functions, we need a function to print the array as well.
The print function is as follows :
|
1 2 3 4 5 6 7 |
static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } |
Using these three functions we can successfully implement Heapsort.
Complete Code
The complete code for Heapsort is as follows :
1. Heap Sort in Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
package com.JournalDev; public class Main { static void downheapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; // finding the maximum of left and right if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; //swapping if child >parent if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; downheapify(arr, n, largest); } } public static void sort(int arr[]) { int n = arr.length; //build heap by calling heapify on non leaf elements for (int i = n / 2 - 1; i >= 0; i--) downheapify(arr, n, i); //extract elements from the root and call healpify for (int i=n-1; i>0; i--) { // swap the last element with root int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // i is the size of the reduced heap downheapify(arr, i, 0); } } static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } public static void main(String[] arg) { int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2}; int n = arr.length; sort(arr); System.out.println("Sorted array is"); printArray(arr); } } |
2. Heap Sort in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> using namespace std; void downheapify(int arr[], int n, int i) { int largest = i; int l = 2*i + 1; int r = 2*i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest != i) { swap(arr[i], arr[largest]); downheapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i=n-1; i>0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } void printArray(int arr[], int n) { for (int i=0; i<n; ++i) cout << arr[i] << " "; cout << "n"; } int main() { int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2}; int n = sizeof(arr)/sizeof(arr[0]); heapSort(arr, n); cout << "Sorted array is n"; printArray(arr, n); } |
|
1 2 3 4 |
<span style="color: #008000;"><strong>Output : Sorted array is 1 1 2 2 2 3 4 10 23 100</strong></span> <img class="alignnone wp-image-29843 size-full" src="http://all-learning.com/wp-content/uploads/2020/08/heapsort1.png" alt="heapsort" width="1200" height="628" /> |
Conclusion
This is how you can implement Heapsort in Java/C++. The time complexity of Heapsort is O(log(n)). Heapsort is a better sorting algorithm as compared to bubble sort, insertion sort, selection sort and even quick sort.