Heap Sort

Category: Sorting

The problem

This repo's Merge Sort guarantees O(n log n) but needs an O(n) auxiliary buffer. Quick Sort sorts in place with average-case O(n log n), but even with a randomized pivot the worst case is still mathematically real. Neither one gives both guarantees at once — a bound that holds unconditionally, and zero auxiliary memory.

The solution

Treat the array itself as a binary heap. First rearrange it in place into a max-heap (bottom-up, O(n) total), so the largest not-yet-placed value always sits at index 0. Then repeatedly swap that root with the last not-yet-sorted slot and sift the new root back down to restore the heap property, shrinking the "still a heap" region by one each time. Every sift-down touches at most log2(size) levels, done n times: O(n log n), and because a binary heap stored in an array needs no pointers and no separate structure — parent/child relationships are pure index arithmetic — the whole thing happens in the original array with zero auxiliary allocation.

flowchart TD
    subgraph "max-heap after heapify"
        direction TB
        R["9"] --> L["7"]
        R --> Rt["8"]
        L --> LL["3"]
        L --> LR["5"]
    end

Classic example

classic/HeapSort is generic over Comparator<? super T> — no Arrays.sort/Collections.sort shortcut, and no java.util.PriorityQueue either, since the whole point is building the heap directly on top of the array being sorted rather than a separate structure. HeapSortTest covers an unordered array, already-sorted, reverse-sorted, duplicates, both an odd- and an even-sized array (exercises both the left-only and left+right sift-down branches), a single-element and an empty array, a custom (descending) comparator, and both null-argument guards.

Applied example: telecom edge-equipment alarm sort

applied/NetworkAlarmSort sorts a batch of network alarms by severity, highest first, on constrained telecom edge equipment — the one place among this repo's sorting modules where "guaranteed O(n log n)" and "zero auxiliary memory" both matter at the same time, not just one or the other. Merge sort's O(n) buffer risks an allocation the device's tight RAM budget can't always absorb; even a randomized quicksort's worst-case risk is a real-time-processing constraint this alarm-handling loop can't accept. Heap sort is the one sort in this repo that gives up neither guarantee. NetworkAlarmSortTest covers descending ordering by severity, that the input array is left untouched, and the null-argument guard.

Benchmark

./gradlew :sorting:heap-sort:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Same three orderings and sizes as this repo's Merge Sort benchmark:

Same story as Merge Sort: all three orderings land within ~1.3x of each other at every size — heap shape depends on how many elements there are, not what order they arrived in, so the guarantee holds regardless of input order. Growth confirms O(n log n) too: random goes from size=1,000 to size=10,000 (10x the data) at ~15.0x the cost, matching the ~13.3x an O(n log n) shape predicts, not the ~100x a quadratic sort would show. Comparing absolute numbers against Merge Sort and Quick Sort on this same machine at size=10,000 (heap sort ~1,676–2,247 µs vs. merge sort's ~935–1,683 µs and quicksort's ~1,002–2,171 µs): heap sort runs in the same ballpark but isn't the fastest of the three — the well-known reason is cache locality. A binary heap's parent/child index jumps (2i+1, 2i+2) touch memory less predictably than merge sort's sequential scans or quicksort's localized partitioning, so heap sort typically loses a constant-factor race it wins on paper (same Big-O) but not always in wall-clock time. Same guarantee, real-world cost that Big-O alone doesn't capture.

When not to use it

• Don't actually need the in-place guarantee, and want the best typical-case wall-clock time? Quick Sort usually edges out heap sort on non-adversarial input, for the cache-locality reason explained above.
• Need stability (equal elements keeping their original order)? Heap sort doesn't provide it — Merge Sort does.
• Already have this repo's Heap / Priority Queue structure in hand for a different reason (e.g. ongoing insert/extract-min traffic, not a one-shot sort)? Reuse it directly instead of re-heapifying a plain array from scratch here.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :sorting:heap-sort:jacocoTestReport

Report at sorting/heap-sort/build/reports/jacoco/test/html/index.html.

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Chapter 6, "Heapsort" — the formal treatment of build-heap's O(n) bound (not the naive O(n log n) a per-element insert count would suggest) and the extraction loop this module implements.
• Sedgewick & Wayne — Algorithms, 4th ed., Chapter 2.4, "Priority Queues" — covers heap sort alongside the broader priority-queue API it's built from.

Unit tests

package com.algorithms.sorting.heapsort.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class HeapSortTest {

    @Test
    void sortsAnUnorderedArrayIntoAscendingOrder() {
        Integer[] array = {5, 3, 8, 1, 9, 2, 7, 4, 6};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5, 6, 7, 8, 9);
    }

    @Test
    void alreadySortedArrayStaysSorted() {
        Integer[] array = {1, 2, 3, 4, 5};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void reverseSortedArrayEndsUpAscending() {
        Integer[] array = {5, 4, 3, 2, 1};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void duplicatesAreHandledCorrectly() {
        Integer[] array = {3, 1, 3, 2, 1};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 1, 2, 3, 3);
    }

    @Test
    void evenSizedArraySortsCorrectly() {
        Integer[] array = {8, 1, 6, 3};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 3, 6, 8);
    }

    @Test
    void singleElementArrayStaysUnchanged() {
        Integer[] array = {42};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(42);
    }

    @Test
    void emptyArrayStaysEmpty() {
        Integer[] array = {};

        HeapSort.sort(array, Comparator.naturalOrder());

        assertThat(array).isEmpty();
    }

    @Test
    void sortsUsingACustomComparatorForDescendingOrder() {
        Integer[] array = {1, 5, 3, 2, 4};

        HeapSort.sort(array, Comparator.reverseOrder());

        assertThat(array).containsExactly(5, 4, 3, 2, 1);
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> HeapSort.sort(null, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> HeapSort.sort(new Integer[] {1, 2}, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.sorting.heapsort.applied;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class NetworkAlarmSortTest {

    @Test
    void sortBySeverityDescendingOrdersHighestFirst() {
        NetworkAlarmSort sorter = new NetworkAlarmSort();
        NetworkAlarm[] alarms = {
                new NetworkAlarm("low", 2),
                new NetworkAlarm("critical", 9),
                new NetworkAlarm("mid", 5),
        };

        NetworkAlarm[] sorted = sorter.sortBySeverityDescending(alarms);

        assertThat(sorted).extracting(NetworkAlarm::alarmId).containsExactly("critical", "mid", "low");
    }

    @Test
    void doesNotMutateTheInputArray() {
        NetworkAlarmSort sorter = new NetworkAlarmSort();
        NetworkAlarm[] alarms = {new NetworkAlarm("b", 1), new NetworkAlarm("a", 9)};

        sorter.sortBySeverityDescending(alarms);

        assertThat(alarms).extracting(NetworkAlarm::alarmId).containsExactly("b", "a");
    }

    @Test
    void rejectsNullAlarms() {
        NetworkAlarmSort sorter = new NetworkAlarmSort();

        assertThatThrownBy(() -> sorter.sortBySeverityDescending(null)).isInstanceOf(IllegalArgumentException.class);
    }
}

View full JaCoCo coverage report →