Heap Sort
Heap Sort
Heap Sort is a efficient and popular sorting algorithm in programming. Heap is a complete binary tree and this tree in which the node can have the atmost two children. A complete binary tree is a binary tree in having levels except the last level, that is leaf node, should be completely filled.
The concept of this sort is to eliminate the elements one by one from the heap of the list, and then insert them into the sorted part of the list.
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
Working of Heap sort Algorithm
Working of the Heapsort Algorithm.
In heap sort generally, there are two phases in the sorting of elements. By using the heap sort algorithm, they are following
In first step the creation of a heap by adjusting the elements of the array. And then remove the root element of the heap repeately by shifting it to the end of the array, and after that store the heap structure with the remaining elements.
Example of Heap Sort
Suppose we take an unsorted array and try to sort it using heap.
Firstly, we have to construct a heap from the array and convert it into max heap.
After converting the given heap into max heap, the array elements are
Next, we delete the root element that is 89 from the max heap. To remove this node, we have to swap it with the last node that is 11. After removing the root element, again have to heapify it to convert it into max heap.
After swapping the array element 89 with 11, and converting the heap into the max-heap, then the elements of array are as follows
In the next step again we delete the root element 81 from the max heap. To delete this node we have to swap it with the 54 i.e last node. After deleting the root element, heapify is convert into max heap.
After swapping the array element 81 with 54 and converting the heap into max-heap, the elements of array are given below-
In the next step, we have to remove the 76 i.e. root element from the max heap again. To delete this node, we have to swap it with the 9 i.e.last node. After deleting the root element, we again have to heapify it to convert it into max heap.
After swapping the element 76 with 9 and converting the heap into max-heap, the elements of array are given below
After that, again we have to remove the 54 i.e root element from the max heap. To remove this node, swap it with the 14 i.e last node .After deleting the root element,heapify is convert into max heap.
After swapping the element 54 with 14 and converted the heap into max-heap, the elements of array are given below
In the next step, we have to remove the 22 i.e root element from the max heap. To remove this node, swap it with the 11i i.e last node.After removing the root element, heapify it to convert it into max heap.
After swapping the array element 22 with 11 and converting the heap into max-heap, the elements of array are given below –
In the next step, again we have to remove the 14 i.e.root element from the max heap. To remove this node, swap it with the 9 i.e last node. After removing the root element, heapify it to convert it into max heap.
After swapping the array element 14 with 9 and converting the heap into max-heap, the elements of array are given by-
In the next step, again we have to remove the 11 i.e root element from the max heap. To remove this node,swap it with the 9 i.e. last node. After removing the root element, heapify it to convert it into max heap.
After swapping the array element 11 with 9 the elements of array are given below-
Heap have only one element left. After removing it, heap will be empty.
After completion of sorting the array elements are given below –
The array is completely sorted.
Program of Heap sort in C
#include <stdio.h>
// Function to swapping
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
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;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function
void heapSort(int arr[], int n) {
// 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
heapify(arr, i, 0);
}
}
// Printing an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is \n");
printArray(arr, n);
}
Output
Sorted array is 1 5 6 9 10 12
Program of Heap sort in C++
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
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
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// main function
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(arr, i, 0);
}
}
// Printing an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver code
int main() {
int arr[] = {1, 12, 9, 5, 6, 10};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}
Output
Sorted array is 1 5 6 9 10 12
Program of Heap sort in Python
def heapify(arr, n, i):
# largest root
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print("%d " % arr[i], end='')
Output
Sorted array is 1 5 6 9 10 12
Program of Heap sort in Java
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// 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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
// largest root and children
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;
// Swap
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
// Function
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver code
public static void main(String args[]) {
int arr[] = { 1, 12, 9, 5, 6, 10 };
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
Output
Sorted array is 1 5 6 9 10 12
Heap sort complexity
1. 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
- The best-case time complexity of heapsort is O(n logn).
- Average Case Complexity – The average case time complexity of heap sort is O(n log n).
- Worst Case Complexity – The worst-case time complexity of heap sort is O(n log n).
The time complexity of heap sort is O(n logn) .
The height of complete binary tree having n elements is logn.
2. Space Complexity
| Space Complexity | O(1) |
| Stable | N0 |
- The space complexity of Heap sort is O(1).
Also read, Bucket Sort