Heap Sort

// 1) The algorithm
// • Build a max-heap from the array (heapify)
// • Swap root (max) with last element; shrink heap; sift down
// • Repeat until heap empty
// • Result: array sorted ascending

function heapsort(arr) {
    const n = arr.length;
    buildMaxHeap(arr);
    for (let end = n - 1; end > 0; end--) {
        [arr[0], arr[end]] = [arr[end], arr[0]];   // move max to end
        siftDown(arr, 0, end);                       // restore heap on remaining
    }
    return arr;
}

function buildMaxHeap(arr) {
    const n = arr.length;
    for (let i = (n >> 1) - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }
}

function siftDown(arr, i, end) {
    while (true) {
        const left  = 2 * i + 1;
        const right = 2 * i + 2;
        let largest = i;
        if (left  < end && arr[left]  > arr[largest]) largest = left;
        if (right < end && arr[right] > arr[largest]) largest = right;
        if (largest === i) return;
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        i = largest;
    }
}

// 2) Complexity
// Time:    O(n log n)  — best, average, worst
// Space:   O(1)        — in-place
// Stable:  no          — siftDown swaps equal elements arbitrarily
// Adaptive: no

// vs quicksort (typical average O(n log n), worst O(n²)):
//   • Heapsort has NO bad worst case → real-time + adversarial-input scenarios
//   • Quicksort is faster in practice (better cache behavior) on random input
//   • Mergesort uses O(n) extra space; heapsort doesn't

// 3) Quick build vs heapify each insertion
// Building a heap from the whole array is O(n), not O(n log n).
// Inserting one-at-a-time would be O(n log n). buildMaxHeap is the right shape.

// 4) Min-heap version — descending sort
function siftDownMin(arr, i, end) {
    while (true) {
        const left  = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;
        if (left  < end && arr[left]  < arr[smallest]) smallest = left;
        if (right < end && arr[right] < arr[smallest]) smallest = right;
        if (smallest === i) return;
        [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
        i = smallest;
    }
}

function heapsortDesc(arr) {
    const n = arr.length;
    for (let i = (n >> 1) - 1; i >= 0; i--) siftDownMin(arr, i, n);
    for (let end = n - 1; end > 0; end--) {
        [arr[0], arr[end]] = [arr[end], arr[0]];
        siftDownMin(arr, 0, end);
    }
    return arr;
}

// 5) Heap data structure — beyond sort
// PriorityQueue:
class MaxHeap {
    constructor() { this.heap = []; }
    push(v) {
        this.heap.push(v);
        let i = this.heap.length - 1;
        while (i > 0) {
            const parent = (i - 1) >> 1;
            if (this.heap[parent] >= this.heap[i]) break;
            [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
            i = parent;
        }
    }
    pop() {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            siftDown(this.heap, 0, this.heap.length);
        }
        return top;
    }
    peek() { return this.heap[0]; }
    size() { return this.heap.length; }
}

const pq = new MaxHeap();
[3, 1, 4, 1, 5, 9, 2, 6].forEach((x) => pq.push(x));
while (pq.size()) console.log(pq.pop());           // 9 6 5 4 3 2 1 1

// 6) Top-K via min-heap (size K)
// Keep the K largest seen so far in a min-heap. New element bigger than min → pop + push.
function topK(items, k) {
    const heap = new MinHeap();
    for (const x of items) {
        if (heap.size() < k) heap.push(x);
        else if (x > heap.peek()) { heap.pop(); heap.push(x); }
    }
    return [...heap.heap].sort((a, b) => b - a);
}

// Time:  O(n log k) — much better than O(n log n) for k << n

// 7) Heap-based interval scheduling, k-way merge, Dijkstra, A* — all use a heap
function kWayMerge(lists) {
    const heap = new MinHeap();
    lists.forEach((list, i) => {
        if (list.length) heap.push({ value: list[0], from: i, idx: 0 });
    });
    const result = [];
    while (heap.size()) {
        const { value, from, idx } = heap.pop();
        result.push(value);
        if (idx + 1 < lists[from].length) {
            heap.push({ value: lists[from][idx + 1], from, idx: idx + 1 });
        }
    }
    return result;
}

// 8) Practical use cases
//   • Real-time systems where O(n²) is unacceptable
//   • Embedded / memory-constrained — no allocation
//   • Top-K problems
//   • Priority queues (event simulation, task scheduling)
//   • Median / running statistics (two heaps)
//   • Dijkstra / A* / Prim shortest path
//
// In production, stdlib sort is usually merge-based (TimSort) or quicksort hybrid.
// Heapsort shines as a worst-case fallback (introsort = quicksort + heapsort).

// 9) Floyd's optimisation — pop without full upward fix
// When popping, sift the LAST element straight down to a leaf (not checking against new descendants),
// then sift up. ~25% fewer comparisons; rarely written by hand.

// 10) Common bugs
// • Off-by-one in left/right child indices — left = 2i+1, right = 2i+2 (0-indexed)
// • Starting buildMaxHeap from the wrong index — start at floor((n-1)/2) or (n>>1)-1
// • Forgetting to decrease 'end' after extraction — sorts incorrectly
// • Inconsistent comparator with custom keys — sometimes returns string compare; pass a function
// • Using siftUp during sort phase — only siftDown is needed after swap
// • Comparing objects with default < — undefined order; provide a comparator
// • Heapsort labelled 'unstable' but team relies on stability — switch to mergesort or TimSort
// • Treating heap as binary search tree — heap has only PARENT > CHILD invariant; siblings unordered

// O(n log n) in-place, no recursion. Heapify into a max-heap, then pop to the back.
// Useful when you need worst-case O(n log n) without quicksort's pathological cases.