Heap Sort

Heapsort (Heapsort) is a kind of sorting algorithm designed by using the heap data structure. A heap is an almost complete binary tree structure, but also satisfies the property of a heap: the key value or index of a child node is always less than (or greater than) its parent node.

Algorithm description

• The initial sequence of keywords to be sorted (R1,R2... .Rn) builds a large top heap, which is the initial disordered region;
• Swap the top element R[1] with the last element R[n] to get a new unordered region (R1,R2,... Rn-1) and a new ordered region (Rn), satisfying R[1,2... n-1]< =R[n];
• Since the new top R[1] may violate the nature of the heap after exchange, it is necessary to adjust the current disorder region (R1,R2,... Rn-1) adjusts to the new heap, then swaps R[1] again with the last element of the unordered area, giving a new unordered area (R1,R2... .Rn-2) and the new ordered region (RN-1,Rn). Repeat this process until the number of elements in the ordered area is n-1, then the sorting process is complete.
• Use large root piles in ascending order and small root piles in descending order

Animation

Code demo

class Heap {
  value: Array<number>;
  size: number;
  constructor(arr: Array<number> = []) {
    this.value = [...arr];
    this.size = arr.length;
    this.buildMaxHeap();
  }
  swap = (i: number, j: number) => {
    if (this.value[i] === this.value[j]) return;
    this.value[i] = this.value[i] ^ this.value[j];
    this.value[j] = this.value[i] ^ this.value[j];
    this.value[i] = this.value[i] ^ this.value[j];
  };
  heapHandler = (i: number) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;
    if (left < this.size && this.value[left] > this.value[largest]) {
      largest = left;
    }
    if (right < this.size && this.value[right] > this.value[largest]) {
      largest = right;
    }
    if (largest !== i) {
      this.swap(i, largest);
      this.heapHandler(largest);
    }
  };
  buildMaxHeap = () => {
    for (let i = this.size >> 1; i >= 0; i--) {
      this.heapHandler(i);
    }
    for (let i = this.size - 1; i >= 0; i--) {
      this.swap(0, i);
      this.size--;
      this.heapHandler(0);
    }
  };
}

/**
 * @description: Heap Sort
 * @param {Array} list
 * @return {Array}
 */
const heap = (list: Array<number>): Array<number> => {
  const { value } = new Heap(list);
  return value;
};

Algorithm analysis

Heap sort is not stable — swapping the root with the last unsorted element during heapify can reorder equal elements — but it sorts in place, needing only O(1) extra space beyond the array itself. Unlike quicksort, its time complexity is O(n log n) in the best, average, and worst case, since building and re-heapifying the heap costs O(log n) per element regardless of the input's initial order; unlike merge sort, it gets that guarantee without any O(n) auxiliary buffer.