Heap Sort is a comparison-based sorting algorithm that leverages a binary heap data structure to sort elements. It first builds a max heap from the input array, then repeatedly extracts the maximum element and places it at the end of the array. Heap Sort has a time complexity of O(n log n) and sorts in-place, making it memory-efficient, though it is not a stable sort.
Understanding the Problem
Heap Sort involves two main steps: building a heap from the array and then repeatedly removing the root of the heap to obtain a sorted sequence. Maintaining the heap property during extraction requires shifting elements appropriately, and incorrect indexing in the heap can break the sorting process. The algorithm works efficiently for large datasets due to its predictable O(n log n) performance.
Program: Heap Sort
This program demonstrates sorting an integer array in ascending order using Heap Sort.
#include <stdio.h>
// Function to swap two integers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Heapify a 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 index
int right = 2 * i + 2; // Right child index
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i) {
swap(&arr[i], &arr[largest]);
// Recursively heapify the affected subtree
heapify(arr, n, largest);
}
}
// Heap Sort function
void heapSort(int arr[], int n) {
// Build max heap
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--) {
swap(&arr[0], &arr[i]); // Move current root to end
heapify(arr, i, 0); // Heapify reduced heap
}
}
// Function to display array
void display(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Original array: ");
display(arr, n);
heapSort(arr, n);
printf("Sorted array: ");
display(arr, n);
return 0;
}This program builds a max heap from the array and then repeatedly moves the largest element to the end while maintaining the heap property. The heapify function ensures that the subtree rooted at each index satisfies the max-heap condition.
FAQs
Q1: What is the time complexity of Heap Sort?
O(n log n) for best, average, and worst cases.
Q2: Is Heap Sort stable?
No, Heap Sort is not stable.
Q3: How much extra memory does Heap Sort require?
Heap Sort sorts in-place, requiring O(1) additional space.
Q4: When is Heap Sort preferred?
Heap Sort is useful for large datasets where memory efficiency is important and predictable O(n log n) performance is needed.
Conclusion
Heap Sort is a powerful in-place sorting algorithm that leverages the heap data structure to provide predictable O(n log n) performance. While not stable, its efficiency and memory advantage make it suitable for large datasets. Understanding Heap Sort also provides insight into binary heaps and priority queue operations.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A respected and traditional textbook covering fundamental C concepts and core data structures, including heap sort.
- Heap Sort – GeeksforGeeks – A clear explanation of the heap sort algorithm, showing how we build a max-heap, then swap and heapify to sort in place.
- Heap Sort – Programiz – Practical guide that visualizes heap sort working on arrays, links array indices to heap tree nodes, and includes C examples.
- Heap Sort Algorithm – Tutorialspoint – Walks through building a heap, extracting the root, heapifying again, and repeating until sorted, with supporting diagrams and pseudocode.
- Heap Data Structure – GeeksforGeeks – Explores the heap as a complete binary tree and its properties, key for understanding how heap sort works.
- Exploring Time and Space Complexities of Heap Sort – Programiz PRO – Analysis of heap sort’s O(n log n) time complexity across all cases and its in-place nature leading to O(1) auxiliary space usage.
- Heapsort – Wikipedia – Technical deep-dive covering performance stats (time and space), history, algorithm variants, and comparisons with other sorts like quicksort and merge sort.
