Heap Sort in Java
Problem
A max-heap is a complete binary tree, stored here inside the array itself, in which every parent is at least as large as its children — so the largest value is always at the root.
Given an array of integers, sort it in ascending order using heap sort.
Java Program
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {15, 3, 22, 8, 11, 6};
int n = arr.length;
// Build a max-heap: sift down every parent, starting from the last one
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(arr, n, i);
}
// Move the max (root) to the end, then repair the heap on what's left
for (int end = n - 1; end > 0; end--) {
int temp = arr[0];
arr[0] = arr[end];
arr[end] = temp;
siftDown(arr, end, 0);
}
System.out.println(Arrays.toString(arr));
}
static void siftDown(int[] arr, int size, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest == i) return; // parent already beats both children
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
i = largest; // keep sinking the same value
}
}
}Output
Core Logic
Once the array is a max-heap, its largest value sits at index 0; swapping it to the end and repairing the heap on the remaining elements locks in one sorted value per step.
- 1For index
i, the children live at2 * i + 1and2 * i + 2, so the array can be treated as a tree without extra memory. - 2The build phase calls
siftDownon every parent fromn / 2 - 1down to0, turning the whole array into a max-heap. - 3
siftDownswaps a value with its larger child until it is bigger than both children or reaches a leaf. - 4The sort phase swaps the root with
arr[end], shrinks the heap by one, and sifts the new root down — repeating until one element is left.
22 is at the root; it is swapped to the last index, and sifting down brings 15 to the root for the next swap.Key Point: Heap sort guarantees O(n log n) even in the worst case and needs no extra array, but it is not stable — the long-distance swaps can reorder equal values.
Why: Building the heap takes O(n), then each of the n removals sifts down at most log n levels; all swaps happen inside the original array.
Key Concepts
Approach 2: Using PriorityQueue
import java.util.Arrays;
import java.util.PriorityQueue;
public class HeapSortPriorityQueue {
public static void main(String[] args) {
int[] arr = {15, 3, 22, 8, 11, 6};
PriorityQueue<Integer> heap = new PriorityQueue<>(); // a ready-made min-heap
for (int value : arr) {
heap.offer(value);
}
for (int i = 0; i < arr.length; i++) {
arr[i] = heap.poll(); // always hands back the smallest remaining value
}
System.out.println(Arrays.toString(arr));
}
}
Output
Core Logic
Java's PriorityQueue is already a binary min-heap, so adding every value and then removing them one at a time yields them in ascending order.
- 1A
PriorityQueue<Integer>is created with natural ordering, which makes it a min-heap. - 2Each array value is added with
offer(). - 3
poll()always removes the smallest remaining value. - 4Writing the polled values back into
arrin order leaves it sorted.
poll() returns 3, the next returns 6, and so on until the queue is empty.Key Point: This is the quickest way to get heap-sort behaviour in real code, but it boxes every int into an Integer and uses O(n) extra memory — the manual version is what interviewers usually expect.
Why: Each of the n offers and n polls costs O(log n), and the queue holds a separate copy of every value.
Key Concepts
Interview Questions
Is heap sort stable?
No. Swapping the root with the last element can move equal values past each other.
Why is heap sort used less than quick sort in practice?
It has a guaranteed O(n log n) worst case, but its memory access pattern jumps around the array, so quick sort is usually faster on real hardware.