Sorting Algorithms- 4 - Algorithms - Computer Science Engineering (CSE)
Heap Sort
Heap sort is a comparison-based sorting technique that uses the binary heap data structure. It is similar in spirit to selection sort: repeatedly select the largest (or smallest) remaining element and place it in its final position. Heap sort first builds a heap from the input, then repeatedly removes the root (the maximum for a max-heap) and restores the heap property on the remaining elements.
Binary heap: definition and properties
Complete binary tree: a binary tree in which every level, except possibly the last, is completely filled and all nodes are as far left as possible.
Binary heap: a complete binary tree with a special ordering between parent and children. In a max-heap, every parent node has a value greater than or equal to its children. In a min-heap, every parent node has a value less than or equal to its children. Heaps are most commonly implemented using an array because a complete binary tree can be compactly stored in contiguous memory.
With 0-based array indexing, if a node is at index i then its left child is at index 2*i + 1 and its right child is at index 2*i + 2. The parent of node at index i is at index (i-1)/2 (integer division).
Why use an array representation?
- The array representation is space-efficient because no pointers are needed to represent child/parent relationships.
- Accessing parent and child indices is O(1) arithmetic, which makes heap operations efficient.
- Because the heap is complete, there are no unused "holes" in the array, so storage is compact.
Overview of Heap Sort (for increasing order)
- Build a max-heap from the input array.
- Swap the root (largest element) with the last element of the heap; reduce the heap size by one.
- Restore the heap property by calling heapify on the root.
- Repeat steps 2-3 until the heap size is 1. The array becomes sorted in increasing order.
Heapify and building the heap
Heapify is a procedure that, given an index i in an array and the size n of the heap, ensures that the subtree rooted at i satisfies the heap property, assuming its children already do. Because heapify relies on children already being heaps, building the heap is done in a bottom-up order: call heapify for indices n/2 - 1 down to 0. The index n/2 - 1 is the last non-leaf node in a complete binary tree of size n.
Example: build heap and sort
Input array: 4, 10, 3, 5, 1
Array indices (0-based):
4(0) -- root
/ \
10(1) 3(2)
/ \
5(3) 1(4)
Apply heapify starting from index 1, then index 0.
Heapify at index 1:
Before: 4 10 3 5 1
At index 1, children are at indices 3 and 4 (values 5 and 1).
10 is already larger than its children, so no change.
Heapify at index 0:
Before heapify at 0: 4 10 3 5 1
Compare 4 with children 10 and 3; largest is 10 (index 1).
Swap 4 and 10: 10 4 3 5 1
Now heapify subtree rooted at index 1:
Compare 4 with children 5 and 1; largest is 5 (index 3).
Swap 4 and 5: 10 5 3 4 1
Resulting max-heap: 10 5 3 4 1
Now perform extraction steps to sort:
Swap root and last: 1 5 3 4 10
Heap size becomes 4; heapify root:
Compare 1 with children 5 and 3; swap with 5 -> 5 1 3 4 10
Heapify index 1: compare 1 with child 4; swap -> 5 4 3 1 10
Swap root and last (index 3): 1 4 3 5 10
Heap size becomes 3; heapify root:
Compare 1 with children 4 and 3; swap with 4 -> 4 1 3 5 10
Heapify index 1: no children within heap size 3
Swap root and last (index 2): 3 1 4 5 10
Heap size becomes 2; heapify root:
Compare 3 with child 1; already larger -> 3 1 4 5 10
Swap root and last (index 1): 1 3 4 5 10
Heap size becomes 1 -> sorted array in increasing order: 1 3 4 5 10
Algorithmic details
Heapify (max-heap) pseudocode idea:
Given array arr, size n, index i:
largest = i
l = 2*i + 1
r = 2*i + 2
if l < n="" and="" arr[l]=""> arr[largest]:
largest = l
if r < n="" and="" arr[r]=""> arr[largest]:
largest = r
if largest != i:
swap arr[i] and arr[largest]
heapify(arr, n, largest)
Build-heap: call heapify(arr, n, i) for i from n/2 - 1 down to 0.
Complexity and properties
- Time complexity: Building the heap takes O(n) time. Each extraction costs O(log n) for heapify and there are n extractions in the worst case, so the overall worst-case and average-case time complexity is O(n log n).
- Space complexity: Heap sort is an in-place algorithm; it requires O(1) auxiliary space (ignoring recursion stack if heapify is implemented recursively).
- Stability: Typical implementations of heap sort are not stable (equal elements may change relative order). It is possible to make heap sort stable by using extra information (for example, pair values with original indices), but that increases space or complexity.
- Deterministic worst-case: Heap sort guarantees O(n log n) worst-case time, unlike plain quicksort which can degrade to O(n^2) without precautions (randomization or median-of-three).
Practical comparison
Although heap sort has good worst-case guarantees, in practice quicksort and merge sort are often preferred:
- Quicksort typically has better constants and better cache performance, making it faster on average for many inputs.
- Merge sort is stable and performs well on linked lists or when stability is required; it needs O(n) extra space for arrays (unless an in-place variant is used).
- Heap sort is useful when worst-case time bound and constant auxiliary space are important.
Applications of heap sort and heaps
- Sorting a nearly-sorted (k-sorted) array using a min-heap of size k+1.
- Finding k largest (or smallest) elements in an array efficiently.
- Priority queues: heaps are the standard implementation for priority queues because they support insert and extract-max/extract-min in O(log n).
- Selection problems and algorithms that require repeated extraction of extremal elements.
Code examples
The following implementations perform heap sort by building a max-heap and then repeatedly extracting the maximum. They follow the same logical structure; the detailed syntax varies by language.
C++
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\
";
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \
";
printArray(arr, n);
}
Java
// Java program for implementation of Heap Sort
public class HeapSort {
public void sort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
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 max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
/* A utility function to print array of size n */
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[] = { 12, 11, 13, 5, 6, 7 };
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
Python
# Python program for implementation of heap Sort
# To heapify subtree rooted at index i.
# n is size of heap
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
# See if left child of root exists and is
# greater than root
if l < n and arr[largest] < arr[l]:
largest = l
# See if right child of root exists and is
# greater than root
if r < n and arr[largest] < arr[r]:
largest = r
# Change root, if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify the root.
heapify(arr, n, largest)
# The main function to sort an array of given size
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n//2 - 1, -1, -1):
heapify(arr, n, i)
# One by one extract elements
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0)
# Driver code
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is")
for x in arr:
print(x, end=' ')
# This code is contributed by Mohit Kumra
C#
// C# program for implementation of Heap Sort
using System;
public class HeapSort {
public void sort(int[] arr)
{
int n = arr.Length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
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 max heapify on the reduced heap
heapify(arr, i, 0);
}
}
void heapify(int[] arr, int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
static void printArray(int[] arr)
{
int n = arr.Length;
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
int n = arr.Length;
HeapSort ob = new HeapSort();
ob.sort(arr);
Console.WriteLine("Sorted array is");
printArray(arr);
}
}
// This code is contributed by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program for implementation of Heap Sort
function heapify(&$arr, $n, $i)
{
$largest = $i; // Initialize largest as root
$l = 2*$i + 1; // left = 2*i + 1
$r = 2*$i + 2; // right = 2*i + 2
if ($l < $n && $arr[$l] > $arr[$largest])
$largest = $l;
if ($r < $n && $arr[$r] > $arr[$largest])
$largest = $r;
if ($largest != $i) {
$swap = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $swap;
heapify($arr, $n, $largest);
}
}
function heapSort(&$arr, $n)
{
for ($i = (int)($n / 2) - 1; $i >= 0; $i--)
heapify($arr, $n, $i);
for ($i = $n - 1; $i > 0; $i--) {
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
heapify($arr, $i, 0);
}
}
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; ++$i)
echo ($arr[$i]." ");
}
$arr = array(12, 11, 13, 5, 6, 7);
$n = sizeof($arr)/sizeof($arr[0]);
heapSort($arr, $n);
echo 'Sorted array is ' . "\
";
printArray($arr , $n);
?>
JavaScript
<script>
// JavaScript program for implementation of Heap Sort
function heapify(arr, n, i) {
var largest = i; // Initialize largest as root
var l = 2 * i + 1; // left = 2*i + 1
var r = 2 * i + 2; // right = 2*i + 2
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
var swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
function sort(arr) {
var n = arr.length;
for (var i = Math.floor(n / 2) - 1; i >= 0; i--)
heapify(arr, n, i);
for (var i = n - 1; i > 0; i--) {
var temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
function printArray(arr) {
for (var i = 0; i < arr.length; ++i)
document.write(arr[i] + " ");
}
var arr = [ 12, 11, 13, 5, 6, 7 ];
sort(arr);
document.write( "Sorted array is <br>" );
printArray(arr);
</script>
Output (example from the code samples)
Sorted array is
5 6 7 11 12 13
Notes
- In-place: Heap sort is in-place; it requires only a constant amount of extra memory for swapping.
- Stability: Typical array-based heap sort is not stable. Stability can be achieved by augmenting keys (for example, pair each key with its original index), but that adds memory or complexity.
Time complexity summary
- Heapify: O(log n) per call in the worst case.
- Build-heap: O(n) total (bottom-up method).
- Heap sort overall: O(n log n) worst-case and average-case.
Common applications and use-cases
- Sorting arrays that must be sorted in-place with guaranteed O(n log n) worst-case time.
- Finding the k largest (or smallest) elements using a heap of size k.
- Implementing priority queues (insert, extract-max/extract-min) efficiently.
- Sorting nearly-sorted (k-sorted) arrays using a heap of size k+1.
Snapshots:
Other sorting algorithms (for further study)
QuickSort, Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Radix Sort, Counting Sort, Bucket Sort, Shell Sort, Comb Sort, Pigeonhole Sort
|
81 videos|115 docs|33 tests
|
