Heap Sort

1def heap_sort(a):2    n = len(a)3    # Build a max-heap, deepest parent first4    for i in range(n // 2 - 1, -1, -1):5        sift_down(a, i, n)6    # Repeatedly move the max to the end and shrink the heap7    for end in range(n - 1, 0, -1):8        a[0], a[end] = a[end], a[0]9        sift_down(a, 0, end)10    return a11
12
13def sift_down(a, i, size):14    while True:15        largest = i16        left, right = 2 * i + 1, 2 * i + 217        if left < size and a[left] > a[largest]:18            largest = left19        if right < size and a[right] > a[largest]:20            largest = right21        if largest == i:22            return23        a[i], a[largest] = a[largest], a[i]24        i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)

1function heapSort(a) {2    const n = a.length;3    // Build a max-heap, then repeatedly move the max to the end4    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5    for (let end = n - 1; end > 0; end--) {6        [a[0], a[end]] = [a[end], a[0]];7        siftDown(a, 0, end);8    }9    return a;10}11
12function siftDown(a, i, size) {13    while (true) {14        const left = 2 * i + 1;15        const right = 2 * i + 2;16        let largest = i;17        if (left < size && a[left] > a[largest]) largest = left;18        if (right < size && a[right] > a[largest]) largest = right;19        if (largest === i) return;20        [a[i], a[largest]] = [a[largest], a[i]];21        i = largest;22    }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));

1import java.util.Arrays;2
3public class Main {4    static void heapSort(int[] arr) {5        int n = arr.length;6        // Build a max-heap, deepest parent first7        for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8        // Repeatedly move the max to the end and shrink the heap9        for (int end = n - 1; end > 0; end--) {10            swap(arr, 0, end);11            siftDown(arr, 0, end);12        }13    }14
15    static void siftDown(int[] arr, int i, int size) {16        while (true) {17            int largest = i, l = 2 * i + 1, r = 2 * i + 2;18            if (l < size && arr[l] > arr[largest]) largest = l;19            if (r < size && arr[r] > arr[largest]) largest = r;20            if (largest == i) return;21            swap(arr, i, largest);22            i = largest;23        }24    }25
26    static void swap(int[] arr, int a, int b) {27        int tmp = arr[a];28        arr[a] = arr[b];29        arr[b] = tmp;30    }31
32    public static void main(String[] args) {33        int[] arr = {12, 11, 13, 5, 6, 7};34        System.out.println("Before: " + Arrays.toString(arr));35        heapSort(arr);36        System.out.println("After:  " + Arrays.toString(arr));37    }38}

1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11    while (true) {12        int largest = i, l = 2 * i + 1, r = 2 * i + 2;13        if (l < n && a[l] > a[largest]) largest = l;14        if (r < n && a[r] > a[largest]) largest = r;15        if (largest == i) return;16        std::swap(a[i], a[largest]);17        i = largest;18    }19}20
21void heapSort(std::vector<int>& a) {22    int n = static_cast<int>(a.size());23    // Build a max-heap in place24    for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25    // Repeatedly move the max to the end and shrink the heap26    for (int end = n - 1; end > 0; --end) {27        std::swap(a[0], a[end]);28        siftDown(a, end, 0);29    }30}31
32int main() {33    std::vector<int> data = {12, 11, 13, 5, 6, 7};34    std::cout << "Before: ";35    printVec(data);36    heapSort(data);37    std::cout << "After:  ";38    printVec(data);39    return 0;40}

1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void siftDown(int a[], int n, int i) {9    while (1) {10        int largest = i, l = 2 * i + 1, r = 2 * i + 2;11        if (l < n && a[l] > a[largest]) largest = l;12        if (r < n && a[r] > a[largest]) largest = r;13        if (largest == i) return;14        int tmp = a[i];15        a[i] = a[largest];16        a[largest] = tmp;17        i = largest;18    }19}20
21void heapSort(int a[], int n) {22    // Build a max-heap in place23    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24    // Repeatedly move the max to the end and shrink the heap25    for (int end = n - 1; end > 0; end--) {26        int tmp = a[0];27        a[0] = a[end];28        a[end] = tmp;29        siftDown(a, end, 0);30    }31}32
33int main(void) {34    int data[] = {12, 11, 13, 5, 6, 7};35    int n = sizeof(data) / sizeof(data[0]);36    printf("Before: ");37    printArr(data, n);38    heapSort(data, n);39    printf("After:  ");40    printArr(data, n);41    return 0;42}