Heap sort an array
Sort an integer array in ascending order in place using heap sort.
Course progress
Problem 78 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [12, 11, 13, 5, 6, 7]
Expected output
5 6 7 11 12 13
What is happening?
Build a max heap with 13 at its root, move each current maximum to the array's end, and repair the shrinking heap after every move.
Solution strategy
Build the right mental model
Build a max heap, repeatedly move its largest root to the end, and restore the heap property in the shrinking prefix.
Core concepts
sorting · binary heap
Complexity
Time O(n log n), space O(1).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for heap-sort
using System;
class Program
{
static void Heapify(int[] numbers, int size, int root)
{
while (true)
{
int largest = root;
int left = root * 2 + 1;
int right = left + 1;
if (left < size && numbers[left] > numbers[largest]) largest = left;
if (right < size && numbers[right] > numbers[largest]) largest = right;
if (largest == root) return;
int temporary = numbers[root];
numbers[root] = numbers[largest];
numbers[largest] = temporary;
root = largest;
}
}
static void HeapSort(int[] numbers)
{
for (int root = numbers.Length / 2 - 1; root >= 0; root--)
Heapify(numbers, numbers.Length, root);
for (int end = numbers.Length - 1; end > 0; end--)
{
int temporary = numbers[0];
numbers[0] = numbers[end];
numbers[end] = temporary;
Heapify(numbers, end, 0);
}
}
static void Main()
{
int[] values = { 12, 11, 13, 5, 6, 7 };
HeapSort(values);
Console.WriteLine(string.Join(" ", values));
}
}Knowledge check
Questions students often ask
What is the main idea behind heap sort an array?
Build a max heap, repeatedly move its largest root to the end, and restore the heap property in the shrinking prefix.
What is the time and space complexity of this solution?
Time O(n log n), space O(1).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.