HeapSort는 빠른가요?

여러분, 오늘은 heap-sort 알고리즘으로 연습을 해보겠습니다. "현재 프로젝트에서 보고 싶은 알고리즘의 코드"시리즈의 2번째 게시물이 될 것입니다.
이 알고리즘의 가장 좋은 부분은 최악의 경우 최상의 경우와 동일한 시간이 필요하다는 것입니다 - O(n·log(n)) . 예를 들어 QuickSort은 최상의 경우O(n·log(n))를 갖지만(3방향 파티션 및 동일한 키와 같은 일부 경우에는 O(n)가 있음) 최악의 경우는 O(n2)입니다! 🤯 마찬가지로 좋은 퀵 정렬 구현이 힙 정렬보다 2~3배 빠르다는 점을 언급해야 합니다. 그리고 힙정렬은 불안정한 정렬입니다. 이는 동일한 정렬 항목의 상대적인 순서가 유지되지 않음을 의미합니다.

복잡성: O(n·log(n)) 시간, O(n) 공간.

MinHeap의 시각적 예:

코드에 대한 규칙(일반적으로):

변수에 대한 올바른 이름 선택

올바른 루프 문 선택: for, while, forEach, reduce 등

극단적인 경우에 대한 초과 조건 및 비교를 피하십시오

.

공간 또는 시간 복잡성을 줄이기 위해 돌연변이를 수행해야 하는 경우가 매우 많기 때문에 알고리즘 기능의 부작용을 피하십시오.

/**
 *         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;
  };
}

용법:

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());

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

시리즈의 이전 게시물:

아래 댓글 섹션에서 여러분의 생각을 알려주세요! 😊