Heapify Algorithm in C++
Heap sort is a sorting algorithm in which the elements are processed by creating the min-heap or max-heap with the help of elements in the given array. Min-heap or max-heap shows the ordering of the array in which the root element shows the minimum or maximum element of the array.
Heap Sort perform two main operations recursively-
- Build a heap H using the elements of the array.
- Repeatedly delete the root element of the heap formed in 1st phase.
What is a Heap?
A heap is a complete binary tree, and the binary tree is a tree in which the node can have at most two children. A complete binary tree is a binary tree in which all the levels except the last level, i.e., the leaf node, must be filled completely, and the node in a complete binary tree must be left-justified.
What is Heap Sort?
Heapsort is a popular sorting algorithm that is very efficient. The heap sort is to eliminate the elements one by one from the heap part of the list and then insert them into the sorted part of the list.
It is an in-place sorting algorithm.
Now, let's look at the algorithm of heap sort.
Algorithm
HeapSort(arr)
BuildMaxHeap(arr)
for i = length(arr) to 2
swap arr[1] with arr[i]
heap_size[arr] = heap_size[arr] ? 1
MaxHeapify(arr, 1)
End
BuildMaxHeap(arr)
BuildMaxHeap(arr)
heap_size(arr) = length(arr)
for i = length(arr) / 2 to 1
MaxHeapify(arr, i)
End
MaxHeapify(arr, i)
MaxHeapify(arr, i)
L = left(i)
R = right(i)
if L ? heap_size[arr] and arr[L] > arr[i]
largest = L
else
largest = i
if R ? heap_size[arr] and arr[R] > arr[largest]
largest = R
if largest != i
swap arr[i] with arr[largest]
MaxHeapify(arr, largest)
End
Working of Heap Sort Algorithm
Now, let's see how a heap sort algorithm works.
In heap sort algorithm, basically there are two parts involved in the sorting of elements.
The first set of this algorithm contains the building of a heap by adjusting the elements of the array.
After creating the heap, remove the first element of the heap by repeatedly shifting it to the end of the array and then store the heap structure with the remaining elements.
Now let's look at the working of heap sort with the help of an example. To understand it more clearly, let us take an array that is unsorted, and we try to sort the array with the help of heap sort. This will make our explanation clearer and easier.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp1.png)
First a heap is constructed from the given array, and it is converted into max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp2.png)
After converting the given heap into a max heap, the array elements are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp3.png)
Next, we have to delete the root element (89) from the max heap. To delete this node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp4.png)
After swapping the array element 89 with 11 and converting the heap into max-heap, the elements of the array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp5.png)
In the next step, we have to delete the root element (81) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (54). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp6.png)
After swapping the array element 81 with 54 and converting the heap into max-heap, the elements of the array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp7.png)
In the next step, we have to delete the root element (76) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp8.png)
After swapping the array element 76 with 9 and converting the heap into max-heap, the elements of the array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp9.png)
In the next step, we have to delete the root element (54) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (14). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp10.png)
After swapping the array element 54 with 14 and converting the heap into max-heap, the elements of array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp11.png)
In the next step, we have to delete the root element (22) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp12.png)
After swapping the array element 22 with 11 and converting the heap into max-heap, the elements of the array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp13.png)
In the next step, we have to delete the root element (14) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp14.png)
After swapping the array element 14 with 9 and converting the heap into max-heap, the elements of array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp15.png)
In the next step, we have to delete the root element (11) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into a max heap.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp16.png)
After swapping the array element 11 with 9, the elements of the array are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp17.png)
Now, the heap has only one element left. After deleting it, the heap will be empty.
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp18.png)
After completion of sorting, the array elements are -
![Heapify Algorithm in C++](https://static.tutorialandexample.com/cpp/heapify-algorithm-in-cpp19.png)
Now, the array is completely sorted.
Heap Sort Complexity
Now, let's look at the time complexity of Heap sort in the best case, average case, and worst case. We will also see the space complexity of Heapsort.
Time Complexity
Case | Time Complexity |
Best Case | O(n logn) |
Average Case | O(n log n) |
Worst Case | O(n log n) |
- Best Case Complexity occurs when no sorting is required, i.e. the array is already sorted. The best-case time complexity of heap sort is O(n logn).
- Average Case Complexity occurs when the array elements are in jumbled order that is not properly ascending or properly descending. The average case time complexity of heap sort is O(n log n).
- Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of heap sort is O(n log n).
The time complexity of heap sort is O(n logn) in all three cases (best case, average case, and worst case). The height of a complete binary tree having n elements is long.
Space Complexity
Space Complexity | O(1) |
Stable | No |
The space complexity of the Heap sort is O(1).
Implementation of Heapify Algorithm in C++
Let us now consider the following snippet of code illustrating the implementation of Heapify Algorithm in the C++ Programming Language.
Code:
#include <iostream>
using namespace std;
/* function to heapify a subtree. Here 'i' is the
index of the root node in array a[], and 'n' is the size of the heap. */
void heapify(int a[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
// If the left child is larger than the root
if (left < n && a[left] > a[largest])
largest = left;
// If a right child is larger than the root
if (right < n && a[right] > a[largest])
largest = right;
// If the root is not the largest
if (largest != i) {
// swap a[i] with a[largest]
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
/*Function to implement the heap sort*/
void heapSort(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
// One by one, extract an element from heap
for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}
/* function to print the array elements */
void printArr(int a[], int n)
{
for (int i = 0; i < n; ++i)
{
cout<<a[i]<<" ";
}
}
int main()
{
int a[] = {47, 9, 22, 42, 27, 25, 0};
int n = sizeof(a) / sizeof(a[0]);
cout<<"Before sorting array elements are - \n";
printArr(a, n);
heapSort(a, n);
cout<<"\nAfter sorting array elements are - \n";
printArr(a, n);
return 0;
}
Output:
Before sorting array elements are -
47 9 22 42 27 25 0
After sorting, array elements are -
0 9 22 25 27 42 47