heap sort explained code example

Example 1: heap sort

// @see https://www.youtube.com/watch?v=H5kAcmGOn4Q

function heapify(list, size, index) {
    let largest = index;
    let left = index * 2 + 1;
    let right = left + 1;
    if (left < size && list[left] > list[largest]) {
        largest = left;
    }
    if (right < size && list[right] > list[largest]) {
        largest = right;
    }
    if (largest !== index) {
        [list[index], list[largest]] = [list[largest], list[index]];
        heapify(list, size, largest);
    }
    return list;
}

function heapsort(list) {
    const size = list.length;
    let index = ~~(size / 2 - 1);
    let last = size - 1;
    while (index >= 0) {
        heapify(list, size, --index);
    }
    while (last >= 0) {
        [list[0], list[last]] = [list[last], list[0]];
        heapify(list, --last, 0);
    }
    return list;
}

heapsort([4, 7, 2, 6, 4, 1, 8, 3]);

Example 2: heapify down

Heapify down is used when we remove the top element from a heap. Removal of an element is done by swapping the top element with the last element at the bottom of the tree, removing the last element, and then heapfying the new top element down to maintain the heap property. Because this moves down the heap tree, it must perform two comparisons per iteration, with the left child and the right child elements, then swap with the smaller one. Because of this, heapify down is usually more complex to implement than heapify up.