Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It is an efficient algorithm with a worst-case time complexity of O(n log n).
How Does Heap Sort Work?
Heap Sort works by leveraging the properties of a binary heap to sort an array. Here’s how it works step by step:
Step-by-Step Explanation:
- Build a Max-Heap:
- The first step is to transform the input array into a max-heap, where each parent node is greater than or equal to its child nodes.
- This ensures that the largest element in the array is at the root of the heap (index 0).
Example:
Input Array: [12, 11, 13, 5, 6, 7]
Max-Heap: [13, 11, 12, 5, 6, 7]
- Extract the Maximum Element:
- Swap the root of the heap (largest element) with the last element of the heap.
- Reduce the size of the heap by one (exclude the last element, as it is now sorted).
- Restore the max-heap property by calling the
heapify
function on the root.
Swap[13]
with[7]
:[7, 11, 12, 5, 6, 13]
Heapify:[12, 11, 7, 5, 6, 13]
- Repeat the Process:
- Continue swapping the root with the last unsorted element and heapifying the root until the heap size is 1.
- Swap
[12]
with[6]
:[6, 11, 7, 5, 12, 13]
- Heapify:
[11, 6, 7, 5, 12, 13]
- Swap
[11]
with[5]
:[5, 6, 7, 11, 12, 13]
- Heapify:
[7, 6, 5, 11, 12, 13]
- Sorted Array:
- Once all elements are extracted, the array is sorted in ascending order.
[5, 6, 7, 11, 12, 13]
How Heapify
Works?
The heapify
function ensures that the max-heap property is maintained after each extraction. Here’s how it works:
- Compare the parent node with its left and right child nodes.
- If a child node is larger than the parent, swap the parent with the largest child.
- Recursively apply the
heapify
process to the affected subtree.
Example:
Input Heap: [7, 11, 6, 5, 12, 13]
Heapify at Root (7):
- Compare
7
,11
, and6
. - Swap
7
with11
:[11, 7, 6, 5, 12, 13]
.
Visual Example:
Initial Array: [12, 11, 13, 5, 6, 7]
- Build Max-Heap:
[13, 11, 12, 5, 6, 7]
- Extract Max (13):
[7, 11, 12, 5, 6, 13]
→ Heapify →[12, 11, 7, 5, 6, 13]
- Extract Max (12):
[6, 11, 7, 5, 12, 13]
→ Heapify →[11, 6, 7, 5, 12, 13]
- Extract Max (11):
[5, 6, 7, 11, 12, 13]
→ Heapify →[7, 6, 5, 11, 12, 13]
- Extract Max (7):
[5, 6, 7, 11, 12, 13]
- Extract Max (6):
[5, 6, 7, 11, 12, 13]
Sorted Array: [5, 6, 7, 11, 12, 13]
Heap Sort Program in Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | package com.javacodepoint.sort; public class HeapSort { // Function to sort an array using Heap Sort public static void heapSort( int [] array) { int n = array.length; // Step 1: Build Max-Heap for ( int i = n / 2 - 1 ; i >= 0 ; i--) { heapify(array, n, i); } // Step 2: Extract elements from the heap one by one for ( int i = n - 1 ; i > 0 ; i--) { // Move the current root (max) to the end int temp = array[ 0 ]; array[ 0 ] = array[i]; array[i] = temp; // Restore the heap property for the reduced heap heapify(array, i, 0 ); } } // Function to maintain the heap property public static void heapify( int [] array, int heapSize, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1 ; // Left child index int right = 2 * i + 2 ; // Right child index // If left child is larger than root if (left < heapSize && array[left] > array[largest]) { largest = left; } // If right child is larger than largest so far if (right < heapSize && array[right] > array[largest]) { largest = right; } // If largest is not the root if (largest != i) { int temp = array[i]; array[i] = array[largest]; array[largest] = temp; // Recursively heapify the affected subtree heapify(array, heapSize, largest); } } public static void main(String[] args) { int [] numbers = { 12 , 11 , 13 , 5 , 6 , 7 }; System.out.println( "Original Array:" ); for ( int num : numbers) { System.out.print(num + " " ); } // Sort the array using Heap Sort heapSort(numbers); System.out.println( "\nSorted Array:" ); for ( int num : numbers) { System.out.print(num + " " ); } } } |
OUTPUT:
Original Array:
12 11 13 5 6 7
Sorted Array:
5 6 7 11 12 13
Time Complexity:
- Build Max-Heap: O(n)
- Heapify: O(log n)
- Extract Elements: O(n log n)
Overall: O(n log n) in all cases (best, average, worst).
Space Complexity:
- O(1): In-place sorting algorithm.
Also Read: Selection Sort | Insertion Sort | Bubble Sort | Merge Sort