Published: 13 Dec 2024 | Reading Time: 6 min read
Heap sort is an efficient comparison-based sorting algorithm that makes use of the heap data structure. It is a non-recursive sorting technique with a unique approach to sorting elements. This article explores the working of heap sort, its types, advantages and disadvantages, as well as its time complexity and implementation in various programming languages.
Heap sort is a sorting algorithm that follows the heap algorithm to convert a list of unsorted elements into a heap structure, and then sorts the heap. This algorithm has a time complexity of O(n log n), making it suitable for large datasets. Instead of other sorting algorithms such as quicksort or merge sort, heap sort guarantees O(n log n) performance for both best and worst cases, making it a reliable sorting method.
Data structures that satisfy the heap property are specialized binary tree-based structures. Heaps are usually represented as binary heaps and come in two main types:
In a max heap, the value of the parent node is greater than or equal to the values of its children. This ensures that the largest element is always at the root.
Nodes that have a value less than or equal to the value of their children are called min heaps. The smallest node in a min-heap is at the root.
Heaps are typically used to implement priority queues, where the highest or lowest priority element must be accessed quickly.
HeapSort uses the Max-Heap structure to sort an array. The main idea behind HeapSort is to:
The heap sort algorithm uses a binary heap data structure to perform comparison-based sorting. It works in two major phases:
To begin with, we need to convert the given array into a max heap. The max-heap consists of a binary tree in which each parent node is greater than its child nodes. We'll heapify the array starting from the last non-leaf node.
Step 1: The last non-leaf node is at index 3 (element 34). We begin by heapifying this subtree.
After heapifying:
45
/ \
21 67
/ \ / \
34 89 12 56
/ \
90 72
Step 2: We heapify node 67. After heapifying, the array becomes:
45
/ \
67 56
/ \ / \
34 89 12 21
/ \
90 72
Step 3: Now, we heapify node 21. After heapifying, the tree looks like this:
45
/ \
67 56
/ \ / \
89 72 12 21
/ \
90 34
Step 4: Finally, we heapify the root node (45). After heapifying, the array becomes:
90
/ \
89 56
/ \ / \
72 67 12 21
/ \
34 45
Step 5: Finally, the max heap array: [90,89,56,72,67,12,21,34,45]
Now that we have a max-heap, we can start extracting the root (largest element) and placing it at the end of the array.
Let us take an array of max heap to extract the root of the sorted array: [90,89,56,72,67,12,21,34,45]
Step 1: Swap the root with the last element (90 and 45). Then remove the last element (90).
90
/ \
89 56
/ \ / \
72 67 12 21
/ \
34 45
Step 2: The largest child of 45 is 89, so swap 45 with 89. Now the heap is no longer a max heap, so continue heapifying down.
89
/ \
45 56
/ \ / \
72 67 12 21
/ \
34
Step 3: Heapify the subtree rooted at 45. The largest child is 72
89
/ \
72 56
/ \ / \
45 67 12 21
/ \
34
Step 4: Heapify the subtree rooted at 45. Swap the largest child of 45 is 34.
89
/ \
72 56
/ \ / \
34 67 12 21
/ \
45
Step 5: Extract the next root (89), swap with the last element (45), and heapify the root. Now, Swap 89 with 45, and remove 89.
The largest child of 45 is 72, so swap 45 with 72. After heapify:
72
/ \
45 56
/ \ / \
34 67 12 21
Step 6: Heapify the subtree rooted at 45. The largest child of 45 is 67, so swap 45 with 67.
72
/ \
67 56
/ \ / \
34 45 12 21
Step 7: Extract the next root (72), swap with the last element (21), and heapify the root.
67
/ \
45 56
/ \ /
34 21 12
Step 8: Now, heapify the subtree rooted at 21. Since the largest child of 21 is 34, swap 21 with 34.
67
/ \
45 56
/ \
34 21
Step 9: Extract the next root (67), swap with the last element (12), and heapify the root.
56
/ \
45 12
/ \
34 21
Step 10: Finally, by performing all steps we get a sorted array is [12,21,34,45,56,67,72,89].
Here are the programs of heap sort in C, C++ and Java language:
#include <stdio.h>
// Function to heapify the subtree rooted at index i
void heapify(int arr[], 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
// Check if left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// Change root, if needed
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
// Main function to implement heapsort
void heapSort(int arr[], int n) {
// Build a maxheap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver code
int main() {
int arr[] = {90,89,56,72,67,12,21,34,45};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: \n");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
#include <iostream>
using namespace std;
// Function to heapify the subtree rooted at index i
void heapify(int arr[], 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
// Check if left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// Change root, if needed
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
// Main function to implement heapsort
void heapSort(int arr[], int n) {
// Build a maxheap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
// Driver code
int main() {
int arr[] = {90,89,56,72,67,12,21,34,45};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Unsorted array: \n";
printArray(arr, n);
heapSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
import java.util.*;
public class Heapsort {
// Function to heapify the subtree rooted at index i
public static void heapify(int arr[], 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
// Check if left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// Check if right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// Change root, if needed
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
// Main function to implement heapsort
public static void heapSort(int arr[]) {
int n = arr.length;
// Build a maxheap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
// Function to print the array
public static void printArray(int arr[]) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int arr[] = {90,89,56,72,67,12,21,34,45};
System.out.println("Unsorted array: ");
printArray(arr);
heapSort(arr);
System.out.println("Sorted array: ");
printArray(arr);
}
}
Unsorted array:
90 89 56 72 67 12 21 34 45
Sorted array:
12 21 34 45 56 67 72 89 90
Here are the advantages and disadvantages of Heap Sort in data structures:
Here's an overview of its time complexity and space complexity across different cases:
| Complexity Type | Value |
|---|---|
| Best Case Time Complexity | O(n log n) |
| Worst Case Time Complexity | O(n log n) |
| Average Case Time Complexity | O(n log n) |
| Space Complexity | O(1) |
In conclusion, heap sort is a sorting algorithm based on a binary heap data structure. It has a time complexity of O(n log n) in both the average and worst cases, making it more predictable than algorithms like QuickSort in terms of performance. Heap Sort requires only a constant amount of extra space, which makes it memory efficient. While not stable, its ability to sort efficiently and its suitability for scenarios where memory constraints are important makes it a valuable tool for various applications, especially in priority queue operations.
No, heap sort is not a stable sorting algorithm, meaning that it does not guarantee that equal elements will maintain their relative order.
Heap sort works by building a heap from the input array, then repeatedly extracting the maximum (or minimum) element and rebuilding the heap until the array is sorted.