is HeapSort fast?

Hey guys, today we gonna practice with the heap-sort algorithm.
The best part of that algorithm is in the worst case we need the same time as in the best case - O(n·log(n)). E.g. QuickSort has the best case O(n·log(n)) (in some cases like three-way partition and equal keys has O(n)), but the worst case is O(n2)! 🤯 Likewise, I need to mention that good implementation of quick sort is about two or three times faster than heapsort. And heapsort is an unstable sort this meaning that the relative order of equal sort items is not preserved.

Complexity: O(n·log(n)) time, O(n) space or O(1) for in-place implementations.

Visual example of MinHeap:

Rules for the code (as usual):

1. Choose the right names for variables
2. Choose the right loop statements: for, while, forEach, reduce etc.
3. Avoid excess conditions and comparings for edge cases
4. Escape the side effects in your algorithms function, because very often you need to do mutations to decrease space or time complexity

/**
 *         1
 *       /   \
 *     7      12
 *    / \     /
 *  10  15  25
 */

class MinHeap {
  #heap = [];

  get heap() {
    return this.#heap;
  }

  #getParentIndex = (childIndex) => {
    return Math.floor((childIndex - 1) / 2);
  };

  #hasParent = (index) => {
    return this.#getParentIndex(index) >= 0;
  };

  #getParent = (childIndex) => {
    return this.#heap[this.#getParentIndex(childIndex)];
  };

  #getLeftChildIndex = (parentIndex) => {
    return parentIndex * 2 + 1;
  };

  #getRightChildIndex = (parentIndex) => {
    return parentIndex * 2 + 2;
  };

  #hasLeftChild = (parentIndex) => {
    return this.#getLeftChildIndex(parentIndex) < this.#heap.length;
  };

  #hasRightChild = (parentIndex) => {
    return this.#getRightChildIndex(parentIndex) < this.#heap.length;
  };

  #getLeftChild = (parentIndex) => {
    return this.#heap[this.#getLeftChildIndex(parentIndex)];
  };

  #getRightChild = (parentIndex) => {
    return this.#heap[this.#getRightChildIndex(parentIndex)];
  };

  #isSmaller = (firstElement, secondElement) => {
    return firstElement < secondElement;
  };

  #swap = (firstIndex, secondIndex) => {
    const firstElement = this.#heap[firstIndex];

    this.#heap[firstIndex] = this.#heap[secondIndex];
    this.#heap[secondIndex] = firstElement;
  };

  /**
   * @description
   * Sorting parents
   */
  #heapifyUp = () => {
    // starts from last element
    let currentIndex = this.#heap.length - 1;
    const currentElement = this.#heap[currentIndex];

    while (
      this.#hasParent(currentIndex) &&
      this.#isSmaller(currentElement, this.#getParent(currentIndex))
    ) {
      const parentIndex = this.#getParentIndex(currentIndex);

      this.#swap(parentIndex, currentIndex);
      currentIndex = parentIndex;
    }
  };

  /**
   * @description
   * Sorting leaves
   */
  #heapifyDown = () => {
    let parentIndex = 0;

    while (this.#hasLeftChild(parentIndex)) {
      let smallestChildIndex = this.#getLeftChildIndex(parentIndex);

      if (
        this.#hasRightChild(parentIndex) &&
        this.#isSmaller(this.#getRightChild(parentIndex), this.#getLeftChild(parentIndex))
      ) {
        smallestChildIndex = this.#getRightChildIndex(parentIndex);
      }

      if (this.#heap[parentIndex] < this.#heap[smallestChildIndex]) {
        break;
      } else {
        this.#swap(parentIndex, smallestChildIndex);
      }

      parentIndex = smallestChildIndex;
    }
  };

  add = (item) => {
    this.#heap.push(item);
    this.#heapifyUp();
  };

  poll = () => {
    if (this.#heap.length === 1) {
      return this.#heap.pop();
    }

    const smallerItem = this.#heap[0];
    this.#heap[0] = this.#heap.pop();

    this.#heapifyDown();

    return smallerItem;
  };
}

class HeapSort {
  #inputArray;

  constructor(inputArray) {
    this.#inputArray = inputArray;
  }

  sort = () => {
    const minHeap = new MinHeap();

    this.#inputArray.forEach((item) => {
      minHeap.add(item);
    });

    const sortedArray = [];
    let nextMinElement = minHeap.poll();

    while (Number.isFinite(nextMinElement)) {
      sortedArray.push(nextMinElement);
      nextMinElement = minHeap.poll();
    }

    return sortedArray;
  };
}

Usage:

console.log(new HeapSort([3, 2, 1]).sort());
console.log(new HeapSort([3, 2, 1, 10, 20]).sort());
console.log(new HeapSort([5, 1, 1, 2, 0, 0]).sort());

Sources:
Github heap-sort in js
Test your code on leetcode

Let me know your thoughts in the comment section below! 😊

Comments

[Falcão]

Hey, cool article, just to add: heapsort has a best, average and worst case of O(log n), but as you mentioned, a well-implemented quicksort runs faster in pratice, but heapsort is a cool tool to know, as it is O(1) in space complexity (you need to build the heap first, but you can just use the same array)