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