A nightly sensor dump is an int[] that already fills most of the process. The first version boxed every reading into Integer, offered each one to a PriorityQueue, and polled into a new ArrayList. The numbers came out in order. The heap of objects did not fit next to the original array. Someone called that heapsort. It was a mutable next-best structure copying the data, not a sort of the frozen array they already had.

Build a max-heap, then repeatedly extract the max into the tail — O(n log n) worst case, little extra memory. The array is the heap, then the array is the result. The Heaps post owns the layout: complete tree in an array, heap-order, sift. This post is only the sort procedure that consumes that layout. Families live on the Algorithms Roadmap.

Heapify the range, then peel the max into the tail

Two steps. That is the whole procedure.

  1. Heapify the unordered array into a max-heap: largest at index 0, heap-order on the rest. One linear build, not n inserts.
  2. Extract n - 1 times: swap the root with the last slot of the live heap, shrink the heap by one, restore heap-order on the prefix. The tail grows a sorted suffix, largest to smallest from the right.

After step 1 the extreme is at the root and the rest is not sorted — that is the heap’s point, already argued in the layout post. After each extract, a[end] is the next-largest remaining value and it will not move again. The live prefix a[0 .. end) is a max-heap of what is left. When the prefix is one slot, the array is sorted.

You do not insert into a PriorityQueue. You do not allocate a second buffer for the output. Sift is the same restore the layout post already walked; this loop only names when you call it: once per parent in heapify, once per extract.

Note: Max-heap, not the JDK’s default min-heap. You want the largest remaining key at the root so the tail can fill from the right. A min-heap would fill a sorted prefix from the left with the same idea; textbooks and this walk stay on max.

A walked pass: six readings

Same six values as the billing-adjacent arrays in this wave. Heapify is shown as a result — the siftdown from the last parent is the layout post’s job.

a = [4, 1, 7, 3, 8, 5]
     0  1  2  3  4  5

after heapify (max-heap in the same slots):
  [8, 4, 7, 3, 1, 5]
   8 is root; the array is not sorted

extract into the tail (heap prefix | sorted suffix):
  swap 8 ↔ 5, sift prefix 5 →  [7, 4, 5, 3, 1 | 8]
  swap 7 ↔ 1, sift prefix 4 →  [5, 4, 1, 3 | 7, 8]
  swap 5 ↔ 3, sift prefix 3 →  [4, 3, 1 | 5, 7, 8]
  swap 4 ↔ 1, sift prefix 2 →  [3, 1 | 4, 5, 7, 8]
  swap 3 ↔ 1, sift prefix 1 →  [1 | 3, 4, 5, 7, 8]

sorted: [1, 3, 4, 5, 7, 8]

Each line is one planted maximum. The | is not extra memory; it is the shrinking size you pass to sift. Six elements, five extracts, plus the linear build. Empty input and a singleton are already sorted — heapify is a no-op, the extract loop does not run.

The walk is not stable. Two equal readings that started in a given order can swap during sift. If a later stage assumes “same value, earlier row first,” this procedure already dropped that.

The loop: heapify, then n - 1 extracts

siftDown(a, size, i) is the restore from the Heaps post, scoped to a live prefix of length size. The sort is the two for loops around it.

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(a, n, i);
    }
    for (int end = n - 1; end > 0; end--) {
        int tmp = a[0];
        a[0] = a[end];
        a[end] = tmp;
        siftDown(a, end, 0);
    }
}

static void siftDown(int[] a, int size, int i) {
    while (true) {
        int left = 2 * i + 1;
        if (left >= size) {
            break;
        }
        int best = left;
        int right = left + 1;
        if (right < size && a[right] > a[best]) {
            best = right;
        }
        if (a[best] <= a[i]) {
            break;
        }
        int tmp = a[i];
        a[i] = a[best];
        a[best] = tmp;
        i = best;
    }
}

The first loop starts at the last parent (n / 2 - 1) and walks toward the root: that is heapify, O(n), not n times offer. The second loop plants a[0] at end and restores a max-heap of length end. Comparison is “larger child wins” — max-heap. Flip it and you have a min-heap sort that writes the smallest to the tail, which is the wrong direction unless you reverse afterwards.

Note: siftDown here is inlined so the sort is one file. Do not take that as a second heap tutorial. Parent and child indexes, why the tree is complete, and why peek is a[0] stay on the layout post.

Not a PriorityQueue

PriorityQueue is a binary heap that mutates as jobs arrive and leave. Heapsort is a procedure on a range you already hold and will not use as a scheduler afterwards.

// related idea, different bill — extra nodes, extra wrappers, not in-place
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : a) {
    pq.offer(x);
}
for (int i = 0; i < a.length; i++) {
    a[i] = pq.poll();
}

That drain is “heapify-by-insert plus n extracts” into a different store, then write back. It is O(n log n). It is not the in-place sort. Constants lose: boxed Integer, object header, backing array beside a, min-heap default so you are polling smallest-first (which happens to fill a ascending). The sensor dump that already barely fits cannot afford that copy.

PriorityQueue is a mutable next-best structure, not a sort of a frozen array. Use it when the set changes between peeks — the retry queue in the layout post. Use heapsort when the job is “this array, ordered, little extra memory, worst case O(n log n).”

Iterating a PriorityQueue is still not sorted order. Draining with poll empties it. That sentence is the layout post’s; this one only needs the fork: contract vs sort procedure.

Complexity

Heapify is linear. Each extract is a sift of height O(log n), done n - 1 times. The worst case is the same as the best case up to constants: the tree is complete, so you do not get a quicksort-style degenerate split. Extra memory is a handful of locals. Not stable.

TimeO(n log n) worst case
Extra spaceO(1) besides the array (iterative sift)
StableNo
In-placeYes

Compare to the neighbors in this wave: quicksort is faster in the typical case when the pivot policy behaves, and quadratic when it does not. Merge sort is stable and always O(n log n) with an extra array. Heapsort sits in the corner those two leave: guaranteed O(n log n), tiny extra space, not stable.

In the JDK, this corner usually still loses on wall clock. Dual-pivot (primitives) and Timsort (objects) are cache-friendlier and already tuned. Naming heapsort is a constraint, not a default.

When not to use heapsort — and when you still name it

Skip it when the job is not “guaranteed n log n on this array, little extra RAM”:

  • Production default sort. Arrays.sort on int[] is dual-pivot. On objects it is Timsort. Both beat a textbook heapsort on typical data. Call them.
  • Equal keys must keep input order. Not stable. Object Timsort is the JDK answer; merge sort is the extra-array answer.
  • The set is still mutating. Next-best as jobs arrive is PriorityQueue, not a one-shot heapify.
  • You only needed the k best, not a full order. A bounded heap of size k (layout post: top-k) is a different procedure and a smaller bill.

You still name heapsort when one of these is the actual constraint:

  • Worst-case O(n log n) is a requirement, not a hope — adversarial or already-sorted input must not go quadratic.
  • Extra memory is the budget. Merge sort’s second array does not fit; the sensor dump is the example.
  • Teaching: heapify then extract is how you prove a comparison sort can be in-place and O(n log n) without a pivot policy.

Heapsort is the procedure you reach for when the guarantee and the memory cap are the job. It is not the procedure you reach for because you remember a heap from a course.

A tiny n does not need this name. Insertion on a dozen slots is clearer. The JDK already cuts small slices to insertion inside dual-pivot and Timsort.

JDK: no Heapsort class

There is no java.util.Heapsort. The library does not expose this procedure as a sort.

  • Primitive / object sort: Arrays.sort — dual-pivot or Timsort, not heapsort.
  • Next-best ADT: PriorityQueue — poll-all is a related idea with different constants, and it is not in-place on your array.
int[] readings = {4, 1, 7, 3, 8, 5};
Arrays.sort(readings);                 // Dual-Pivot Quicksort — not heapsort

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : readings) {
    pq.offer(x);
}
while (!pq.isEmpty()) {
    pq.poll();                         // drain; this is not Arrays.sort, and not in-place
}

Call Arrays.sort unless you have the guarantee-and-memory job this post named. Hand-roll the two loops when that job is real, or when you are teaching the procedure. Do not wrap int in Integer so that PriorityQueue can pretend to be a sort.

Collections.sort / List.sort are Timsort on objects. Same rule: not heapsort, and usually what you wanted instead.

Cheat sheet

Job:          sort a frozen array; guaranteed O(n log n); little extra memory
Steps:        heapify max-heap O(n); extract root to tail n-1 times
Layout:       binary heap in the same array — see Heaps post (do not re-learn indexes here)
Invariant:    prefix a[0..end) is a max-heap; suffix a[end..] is sorted largest-first
Stable:       no
In-place:     yes (iterative sift)
Vs PQ:        PriorityQueue mutates; poll-all copies; not this sort
Vs JDK sort:  Arrays.sort is dual-pivot / Timsort — usually faster
JDK:          no Heapsort class
Name it when: worst-case n log n, tiny extra space, or teaching

Do:

  • Heapify once, then plant a[0] at the shrinking tail; max-heap so the suffix fills from the right.
  • Name the constraint first: guaranteed O(n log n) and little extra RAM. That is this procedure.
  • Call Arrays.sort when you do not have a worst-case or memory constraint that forbids it.

Don’t:

  • Box the array into a PriorityQueue and poll and call the result heapsort.
  • Expect stability, or expect the JDK to ship this algorithm as a named sort.
  • Build the heap with n inserts when the whole array is already in hand.

Wrap-up

Heapsort is heapify plus extract: a max-heap in the array you already own, then the root swapped into a growing sorted tail until nothing is left to restore. Worst case is O(n log n). Extra memory is a few locals. It is not stable, and it is not PriorityQueue. The JDK will not call it for you — Arrays.sort is dual-pivot or Timsort, and those usually win on the clock. You still name this procedure when the guarantee and the memory cap are the job, or when you are showing that a heap is enough to sort. The layout stays on the Heaps post; this one only ran it to completion.

Next optional step in the series Rank by frequency when the key universe is small. Counting Sort: Rank by Frequency