Card 04/ 07
Heapsort in Python, Java and TypeScript
One sift-down used by both phases, printing the array after the build and after every extraction.
A heapsort is two loops around one function. The sift-down takes the array, the index to sift from and a bound, and the two phases call it with different bounds: the build with the array's length, each extraction with the boundary of the shrinking heap. The listings below sort 4 7 2 9 5 8, print the heap once it is built and then the heap and the sorted part after every extraction, separated by a bar, and check the result against the built-in sort.
Heapsort with one sift-down shared by both phases, in each language
def heapsort(items: list[int]) -> None:
n = len(items)
for i in range(n // 2 - 1, -1, -1):
sift_down(items, i, n)
print("built:", show(items))
for end in range(n - 1, 0, -1):
items[0], items[end] = items[end], items[0]
sift_down(items, 0, end)
print(f"extracted {items[end]}:", show(items[:end]), "|", show(items[end:]))
def sift_down(items: list[int], i: int, end: int) -> None:
while 2 * i + 1 < end:
child = 2 * i + 1
if child + 1 < end and items[child + 1] > items[child]:
child += 1
if items[i] >= items[child]:
return
items[i], items[child] = items[child], items[i]
i = child
def show(values: list[int]) -> str:
return " ".join(map(str, values))
numbers = [4, 7, 2, 9, 5, 8]
heapsort(numbers)
print("sorted:", show(numbers))
print("built-in:", show(sorted([4, 7, 2, 9, 5, 8])))built: 9 7 8 4 5 2
extracted 9: 8 7 2 4 5 | 9
extracted 8: 7 5 2 4 | 8 9
extracted 7: 5 4 2 | 7 8 9
extracted 5: 4 2 | 5 7 8 9
extracted 4: 2 | 4 5 7 8 9
sorted: 2 4 5 7 8 9
built-in: 2 4 5 7 8 9import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class HeapsortCode {
static void heapsort(int[] items) {
int n = items.length;
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(items, i, n);
}
System.out.println("built: " + join(items, 0, n));
for (int end = n - 1; end > 0; end--) {
swap(items, 0, end);
siftDown(items, 0, end);
System.out.println("extracted " + items[end] + ": " + join(items, 0, end) + " | " + join(items, end, n));
}
}
static void siftDown(int[] items, int i, int end) {
while (2 * i + 1 < end) {
int child = 2 * i + 1;
if (child + 1 < end && items[child + 1] > items[child]) {
child++;
}
if (items[i] >= items[child]) {
return;
}
swap(items, i, child);
i = child;
}
}
static void swap(int[] items, int a, int b) {
int held = items[a];
items[a] = items[b];
items[b] = held;
}
static String join(int[] values, int from, int to) {
return IntStream.range(from, to).mapToObj(index -> String.valueOf(values[index]))
.collect(Collectors.joining(" "));
}
public static void main(String[] args) {
int[] numbers = {4, 7, 2, 9, 5, 8};
heapsort(numbers);
System.out.println("sorted: " + join(numbers, 0, numbers.length));
int[] copy = {4, 7, 2, 9, 5, 8};
Arrays.sort(copy);
System.out.println("built-in: " + join(copy, 0, copy.length));
}
}built: 9 7 8 4 5 2
extracted 9: 8 7 2 4 5 | 9
extracted 8: 7 5 2 4 | 8 9
extracted 7: 5 4 2 | 7 8 9
extracted 5: 4 2 | 5 7 8 9
extracted 4: 2 | 4 5 7 8 9
sorted: 2 4 5 7 8 9
built-in: 2 4 5 7 8 9function heapsort(items: number[]): void {
const n = items.length;
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
siftDown(items, i, n);
}
console.log(`built: ${items.join(" ")}`);
for (let end = n - 1; end > 0; end--) {
swap(items, 0, end);
siftDown(items, 0, end);
console.log(`extracted ${items[end]}: ${items.slice(0, end).join(" ")} | ${items.slice(end).join(" ")}`);
}
}
function siftDown(items: number[], i: number, end: number): void {
while (2 * i + 1 < end) {
let child = 2 * i + 1;
if (child + 1 < end && items[child + 1] > items[child]) {
child++;
}
if (items[i] >= items[child]) {
return;
}
swap(items, i, child);
i = child;
}
}
function swap(items: number[], a: number, b: number): void {
[items[a], items[b]] = [items[b], items[a]];
}
const numbers = [4, 7, 2, 9, 5, 8];
heapsort(numbers);
console.log(`sorted: ${numbers.join(" ")}`);
const builtIn = [4, 7, 2, 9, 5, 8].sort((a, b) => a - b);
console.log(`built-in: ${builtIn.join(" ")}`);built: 9 7 8 4 5 2
extracted 9: 8 7 2 4 5 | 9
extracted 8: 7 5 2 4 | 8 9
extracted 7: 5 4 2 | 7 8 9
extracted 5: 4 2 | 5 7 8 9
extracted 4: 2 | 4 5 7 8 9
sorted: 2 4 5 7 8 9
built-in: 2 4 5 7 8 9All three printed the same lines. The build turned 4 7 2 9 5 8 into 9 7 8 4 5 2, and each extraction moved one more item across the bar, the largest left in the heap.
The highlighted lines are the two calls to the sift-down. The first, in the build, passes n, because the whole array is being made into a heap. The second, in the extraction loop, passes end, the index the root has just been swapped into, so the sift-down treats indices 0 to end − 1 as the heap and leaves the sorted part alone. Inside the sift-down, the child test 2 * i + 1 < end is what enforces that bound, and > picks the larger child, which is what makes it a max-heap. The sort has no recursion, so its extra memory is a few variables whatever n is.
In real code, use the built-in sort. None of the three languages sorts with heapsort alone, because quicksort and merge sort are faster on typical inputs. Heapsort appears as a safety net instead: Java's Arrays.sort on an int[] runs a dual-pivot quicksort and switches a part to heapsort when the recursion grows too deep, which keeps the whole sort O(n log n). A quicksort with that fallback is called an introsort.
← → move through sections and cards