Heap Sort

Heap is a special tree-based data structure. The Heap Sort is a comparison-based sorting method based on the Binary Heap data structure. Similar to Selection Sort, In this method, we move the minimum element to the beginning and everything else in ascending order. We repeat the procedure with each element.

The complexity of Space and Time

Best: O(nlog(n)) time | O(1) space

Average: O(nlog(n)) time | O(1) space

Worst: O(nlog(n)) time | O(1) space

n is the length of the input array.

Input

[8, 5, 1, 9, 5, 6, 2]

Output

[1, 2, 5, 5, 6, 8, 9]

Hint

In position, create two subarrays out of the input array. The second subarray must be sorted at all times and begin with a length of 0., The first subarray is transformed into a maximum (or minimum) heap and must always satisfy the heap property.

Pseudo Code

DEFINE FUNCTION heapSort(array):
    buildMaxHeap(array)
    FOR endIdx IN reversed(range(1, len(array))):
        swap(0, endIdx, array)
        siftDown(0, endIdx - 1, array)
    RETURN array

DEFINE FUNCTION buildMaxHeap(array):
    SET firstParentIdx TO (len(array) - 2) // 2
    FOR currentIdx IN reversed(range(firstParentIdx + 1)):
        siftDown(currentIdx, len(array) - 1, array)

DEFINE FUNCTION siftDown(currentIdx, endIdx, heap):
    SET childOneIdx TO currentIdx * 2 + 1
    WHILE childOneIdx <= endIdx:
        SET childTwoIdx TO currentIdx * 2 + 2 IF currentIdx * 2 + 2 <= endIdx else -1
        IF childTwoIdx > -1 and heap[childTwoIdx] > heap[childOneIdx]:
            SET idxToSwap TO childTwoIdx
        ELSE:
            SET idxToSwap TO childOneIdx
        IF heap[idxToSwap] > heap[currentIdx]:
            swap(currentIdx, idxToSwap, heap)
            SET currentIdx TO idxToSwap
            SET childOneIdx TO currentIdx * 2 + 1
        ELSE:
            RETURN

DEFINE FUNCTION swap(i, j, array):
    SET array[i], array[j] TO array[j], array[i]

Solution in Typescript

function heapSort(array: number[]) {
  buildMaxHeap(array);
  for (let endIdx = array.length - 1; endIdx > 0; endIdx--) {
    swap(0, endIdx, array);
    siftDown(0, endIdx - 1, array);
  }
  return array;
}

function buildMaxHeap(array: number[]) {
  const firstParentIdx = Math.floor((array.length - 2) / 2);
  for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
    siftDown(currentIdx, array.length - 1, array);
  }
}

function siftDown(currentIdx: number, endIdx: number, heap: number[]) {
  let childOneIdx = currentIdx * 2 + 1;
  while (childOneIdx <= endIdx) {
    const childTwoIdx = currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
    let idxToSwap;
    if (childTwoIdx !== -1 && heap[childTwoIdx] > heap[childOneIdx]) {
      idxToSwap = childTwoIdx;
    } else {
      idxToSwap = childOneIdx;
    }
    if (heap[idxToSwap] > heap[currentIdx]) {
      swap(currentIdx, idxToSwap, heap);
      currentIdx = idxToSwap;
      childOneIdx = currentIdx * 2 + 1;
    } else {
      return;
    }
  }
}

function swap(i: number, j: number, array: number[]) {
  const temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

mocha.setup("bdd");
describe("Heap Sort", () => {
  it("Test Case #1", function () {
    const input = [8, 5, 1, 9, 5, 6, 2];
    chai.expect(heapSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]);
  });
  
  it("Test Case #2", function () {
    const input =[5, 3, 1, 2, 4];
    chai.expect(heapSort(input)).to.deep.equal([1,2,3,4,5]);
  });
});

mocha.run();

Demo

https://codepen.io/evalteam/pen/PoOoMME