Heap Sort
A comparison-based sorting algorithm that uses a binary heap data structure. Invented by J. W. J. Williams in 1964, it combines the better attributes of merge sort and insertion sort. Heap sort divides its input into a sorted and an unsorted region, and iteratively shrinks the unsorted region by extracting the largest element and inserting it into the sorted region.
Visualization
Interactive visualization for Heap Sort
Heap Sort Visualization
Interactive visualization with step-by-step execution
Implementation
1function heapSort(arr: number[]): number[] {
2 const sorted = [...arr];
3 const n = sorted.length;
4
5 // Build max heap
6 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
7 heapify(sorted, n, i);
8 }
9
10 // Extract elements from heap one by one
11 for (let i = n - 1; i > 0; i--) {
12 [sorted[0], sorted[i]] = [sorted[i], sorted[0]];
13 heapify(sorted, i, 0);
14 }
15
16 return sorted;
17}
18
19function heapify(arr: number[], n: number, i: number): void {
20 let largest = i;
21 const left = 2 * i + 1;
22 const right = 2 * i + 2;
23
24 if (left < n && arr[left] > arr[largest]) {
25 largest = left;
26 }
27
28 if (right < n && arr[right] > arr[largest]) {
29 largest = right;
30 }
31
32 if (largest !== i) {
33 [arr[i], arr[largest]] = [arr[largest], arr[i]];
34 heapify(arr, n, largest);
35 }
36}Deep Dive
Theoretical Foundation
Heap Sort is a comparison-based sorting algorithm invented by J. W. J. Williams in 1964. It uses a binary heap data structure to efficiently sort elements. The algorithm works in two phases: First, it builds a max-heap from the input array where the parent node is always greater than or equal to its children. Second, it repeatedly extracts the maximum element (root) from the heap, places it at the end of the sorted array, and restores the heap property by heapifying. The heap is a complete binary tree stored as an array where for index i, left child is at 2i+1 and right child is at 2i+2. This array representation allows efficient in-place sorting without extra space. Heap Sort combines the advantages of Merge Sort (guaranteed O(n log n)) and Insertion Sort (in-place with O(1) space).
Complexity
Time
O(n log n)
O(n log n)
O(n log n)
Space
O(1)
Applications
Industry Use
Priority queue implementations (job scheduling, event simulation)
Operating system task scheduling
K-way merge algorithms in external sorting
Systems requiring guaranteed O(n log n) performance
Embedded systems with limited memory
Selection algorithms (finding kth largest/smallest)
Graph algorithms (Dijkstra, Prim using heap)
Memory management (heap allocation strategies)
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.