is HeapSort fast?
Tags: algorithms, javascript, programming, heapsort
Published: 2022-09-27 18:34:54

Hey guys, today we gonna practice with the [heap-sort](https://en.wikipedia.org/wiki/Heapsort) 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](https://en.wikipedia.org/wiki/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)`! :exploding_head: 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.

Visual example of **MinHeap**:
![Example of MinHeap](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nz4wm14so7by3j0meud1.png)

#### 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

```js
/**
 *         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:
```js
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](
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sorting/heap-sort)
[Test your code on leetcode](https://leetcode.com/problems/sort-an-array/)

Let me know your thoughts in the comment section below! :blush: