Heapsort is in place, and $O(n\log n)$. It uses a (binary) heap to manage the sorting.

Heap

Heap is an array object that can be viewed as a nearly complete binary tree.

A heap array object has two attributes

• length - number of elements in the array
• heap-size - how many elements are sorted in the array
• Where $0 \le heapsize \le length$

Heap structure (given index $i$)

• Root - A[1]
• Parent(i) - $\lfloor i/2 \rfloor$
• Left(i) - $2i$
• Right(i) - $2i+1$
• Note: there are two kinds of heap
  • min-heap: $A[Parent(i)] \le A[i]$ - commonly used in priority queue
  • max-heap: $A[Parent(i)] \ge A[i]$ - using this in heapsort

Building a Max-Heap

To build a max-heap, we first need to understand heapify. Max-heapify is to swap the smaller number downward the heap.

Max-Heapify

Runtime: $O(\log n)$

const max_heapify = (A, i) => {
    let l = 2 * i + 1;  // Left child
    let r = 2 * i + 2;  // Right child
    let largest = i;

    if (l < A.heapsize && A[l] > A[largest])
        largest = l;
    
    if (r < A.heapsize && A[r] > A[largest])
        largest = r;
    
    if (largest !== i) {
        [A[i], A[largest]] = [A[largest], A[i]];  // Swap
        max_heapify(A, largest);
    }
};

Build Max-Heap