worldofitech
In this tutorial, you will learn how the heap sort algorithm works. Additionally, you will discover working instances of heap sort in C, C++, Java, and Python.
In this article, you will learn-
What is Heap Sort?
A sorting algorithm works by first getting sorted out the data to be sorted into a special type of binary tree called a heap. The actual heap has, by definition, the largest value at the top of the tree, so the heap sort algorithm should likewise reverse the order. It does this with the accompanying steps:
- Eliminate the highest item (the largest) and replace it with the furthest right leaf. The highest item is put away in an array.
- Restore the heap.
- Repeat stages 1 and 2 until there are no more items left in the heap.
The sorted elements are currently put away in an array.
Heapsort is particularly proficient for data that is now put away in a binary tree. As a rule, nonetheless, the quick sort algorithm is more effective.
Heap Sort is a famous and effective sorting algorithm in computer programming. Learning how to compose the heap sort algorithm requires information on two types of data structures – arrays and trees.
The initial set of numbers that we need to sort is put away in an array for example [10, 3, 76, 34, 23, 32] and subsequent to sorting, we get a sorted array [3,10,23,32,34,76]
Heap sort works by imagining the elements of the array as a unique sort of complete binary tree called a heap.
As a prerequisite, you must know about a complete binary tree and heap data structure.
Relationship between Array Indexes and Tree Elements
A complete binary tree has a fascinating property that we can use to discover the children and parents of any node.
In the event that the index of any element in the array is I, the element in the index 2i+1 will turn into the left child, and the element in the 2i+2 index will turn into the right child. Likewise, the parent of any element at index i is given by the lower bound of (I-1)/2.
Let’s test it out,
Left child of 1 (index 0) = element in (2*0+1) index = element in 1 index = 12 Right child of 1 = element in (2*0+2) index = element in 2 index = 9 Similarly, Left child of 12 (index 1) = element in (2*1+1) index = element in 3 index = 5 Right child of 12 = element in (2*1+2) index = element in 4 index = 6
Let us likewise to affirm that the standards hold for discovering parent of any node
Parent of 9 (position 2) = (2-1)/2 = ½ = 0.5 ~ 0 index = 1 Parent of 12 (position 1) = (1-1)/2 = 0 index = 1
Understanding this mapping of array indexes to tree positions is basic to understanding how the Heap Data Structure functions and how it is used to actualize Heap Sort.
What is Heap Data Structure?
Heap is a special tree-based data structure. A binary tree is said to follow a heap data structure if
- it is a complete binary tree
- All nodes in the tree follow the property that they are greater than their children for example the largest element is at the root and the two its children and smaller than the root, etc. Such a heap is known as a maximum heap. In the event that all things considered, all nodes are smaller than their children, it is known as a min-heap
The accompanying example diagram shows Max-Heap and Min-Heap.
To learn more about it, please visit Heap Data Structure.
How to “heapify” a tree
Beginning from a complete binary tree, we can alter it to turn into a Max-Heap by running a function called heapify on all the non-leaf elements of the heap.
Since heapify uses recursion, it can be hard to grasp. So Let’s first consider how you would heapify a tree with just three elements.
heapify(array)
Root = array[0]
Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
if(Root != Largest)
Swap(Root, Largest)
The example above shows two situations – one in which the root is the largest element and we don’t have to do anything. What’s more, another wherein the root had a larger element as a child and we expected to swap to keep up max-heap property.
In case you’re worked with recursive algorithms before, you’ve presumably recognized that this should be the base case.
Presently let’s think about another situation in which there is more than one level.
The top element isn’t a maximum heap however all the sub-trees are max-heaps.
To keep up the maximum heap property for the whole tree, we should continue to push 2 downwards until it arrives at its correct position.
Accordingly, to keep up the maximum heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root elements over and over until it is larger than its children or it turns into a leaf node.
We can combine both these conditions in one heapify function as
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
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 and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
This function works for both the base case and for a tree of any size. We would thus be able to move the root element to the correct position to keep up the maximum heap status for any tree size as long as the sub-trees are max-heaps.
Build max-heap
To assemble a maximum heap from any tree, we would thus be able to begin heapifying each sub-tree from the base up and end up with a maximum heap after the function is applied to all the elements including the root element.
On account of a complete tree, the first index of a non-leaf node is given by n/2 – 1. Any remaining nodes after that are leaf-nodes and accordingly don’t should be heapified.
In this way, we can assemble a maximum heap as
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
As demonstrated in the above diagram, we start by heapifying the lowest smallest trees and gradually move up until we arrive at the root element.
In the event that you’ve perceived everything till here, congratulations, you are on your way to mastering the Heap sort.
How Heap Sort Works?
- Since the tree satisfies the Max-Heap property, at that point the largest item is put away at the root node.
2. Swap: Remove the root element and put toward the finish of the array (nth position) Put the last item of the tree (heap) at the empty spot.
3. Remove: Reduce the size of the heap by 1.
4. Heapify: Heapify the root elements again so we have the highest element at root.
5. The process is repeated until all the items on the list are sorted.
The code beneath shows the operation.
// Heap sort
for (int i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
// Heapify root element to get highest element at root again
heapify(arr, i, 0);
}
Python, Java, and C/C++ Examples
Python
# Heap Sort in python
def heapify(arr, n, i):
# Find largest among root and children
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 root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build 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 root element
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='')
Java
// Heap Sort in Java
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// 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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify root element
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
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 and continue heapifying if root is not largest
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
// Function to print an array
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);
}
}
C
// Heap Sort in C
#include <stdio.h>
// Function to swap the the position of two elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
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 and continue heapifying if root is not largest
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// Main function to do heap sort
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 root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
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);
}
C++
// Heap Sort in C++
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
// Find largest among root, left child and right child
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 and continue heapifying if root is not largest
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// main function to do heap sort
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 root element to get highest element at root again
heapify(arr, i, 0);
}
}
// Print 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);
}
Heap Sort Complexity
Heap Sort has O(nlog n) time complexities for all the cases ( best case, averge case, and worst scenario).
Let us understand the reason why. The height of a complete binary tree containing n elements is log n
As we have seen before, to completely heapify an element whose subtrees are now max-heaps, we need to continue to comparing the element and its left and right children and pushing it downwards until it arrives at a point where the two of its children are smaller than it.
In the worst-case imaginable, we should move an element from the root to the leaf node making a difference of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst-case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For every element, this again takes log n the worst time since we may need to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is likewise nlog n.
Likewise, since the build_max_heap and heap_sort steps are executed in a steady progression, the algorithmic complexity isn’t multiplied and it stays in the order for nlog n.
Likewise, it performs sorting in O(1) space complexity. Compared and Quick Sort, it has a better worst-case scenario ( O(nlog n) ). Quick Sort has complexity O(n^2) for the worst-case scenario. However, in different cases, Quick Sort is quick. Introsort is an option to heapsort that combines quicksort and heapsort to hold benefits of both: worst-case scenario speed of heapsort and average speed of quicksort.
Heap Sort Applications
Frameworks concerned about security and inserted frameworks, for example, Linux Kernel use Heap Sort as a result of the O(n log n) upper bound on Heapsort’s running time and consistent O(1) upper bound on its auxiliary storage.
In spite of the fact that Heap Sort has O(n log n) time complexity in any event, for the worst-case scenario, it doesn’t have more applications ( compared with other sorting algorithms like Quick Sort, Merge Sort ). Nonetheless, its basic data structure, heap, can be effectively used on the off chance that we need to extract the smallest (or largest) from the list of items without the overhead of keeping the remaining items in the sorted order. For e.g Priority Queues.
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.
