힙(Heap)

이진 트리를 이용한 자료구조로 우선순위가 높은 요소가 먼저 나가기 위해
요소가 삽입, 삭제 될때 즉시 정렬되는 특징이 있습니다.
여러 개의 값들 중 최대값과 최소값을 빠르게 찾아낼 수 있습니다.

주의!
우선순위 큐를 힙이라고 부르기도 하지만 정확히는 아닙니다.
배열을 우선순위에 따라 정렬한다면 이 또한 우선순위 큐입니다.

힙의 특징

• 우선순위가 높은 요소가 먼저 나간다.
• 루트가 가장 큰 값이되는 최대 힙(Max Heap)과 그 반대인 최소 힙(Min Heap)이 있다.
• 자바스크립트에서는 직접 구현해서 사용해야한다.

위와같은 특징으로 인해 힘은 요소를 추가,삭제하는 로직이 핵심이라고 볼 수 있습니다.

힙 요소 추가

1. 요소가 추가될 때는 트리의 가장 마지막 정점에 위치한다.
2. 추가 후 부모 정점보다 우선순위가 높으면 부모와 순서를 바꾼다.
3. 1번과 2번을 반복하여 가장 우선순위가 높은 정점이 루트가 된다.
   -> 완전 이진 트리의 높이는 logN이기때문에 힙의 요소 추가 알고리즘은
   O(logN)의 시간복잡도를 가진다.

  push(value) {
    this.heap.push(value);
    let currIndex = this.heap.length - 1;
    let parrentIndex = Math.floor(currIndex / 2);

    while (parrentIndex !== 0 && this.heap[parrentIndex] < value) {
      const temp = this.heap[parrentIndex];
      this.heap[parrentIndex] = value;
      this.heap[currIndex] = temp;

      currIndex = parrentIndex;
      parrentIndex = Math.floor(currIndex / 2);
    }
  }

힙 요소 제거

1. 요소의 제거는 루트 정점만 가능하다.
2. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
3. 루트 정점의 두 자식중 우선순위가 높은 정점과 바꾼다.
4. 두 자식 정점이 우선순위가 더 낮을 때 까지 반복한다.
   -> 요소 추가와 같이 O(logN)의 시간복잡도를 가진다.

  pop() {
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let currIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (
      this.heap[currIndex] < this.heap[leftIndex] ||
      this.heap[currIndex] < this.heap[rightIndex]
    ) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currIndex];
        this.heap[currIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currIndex = rightIndex;
      } else {
        const temp = this.heap[currIndex];
        this.heap[currIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currIndex = leftIndex;
      }
      leftIndex = currIndex * 2;
      rightIndex = currIndex * 2 + 1;
    }

    return returnValue;
  }

JavaScript 구현

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  push(value) {
    this.heap.push(value);
    let currIndex = this.heap.length - 1;
    let parrentIndex = Math.floor(currIndex / 2);

    while (parrentIndex !== 0 && this.heap[parrentIndex] < value) {
      const temp = this.heap[parrentIndex];
      this.heap[parrentIndex] = value;
      this.heap[currIndex] = temp;

      currIndex = parrentIndex;
      parrentIndex = Math.floor(currIndex / 2);
    }
  }

  pop() {
    const returnValue = this.heap[1];
    this.heap[1] = this.heap.pop();

    let currIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (
      this.heap[currIndex] < this.heap[leftIndex] ||
      this.heap[currIndex] < this.heap[rightIndex]
    ) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currIndex];
        this.heap[currIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currIndex = rightIndex;
      } else {
        const temp = this.heap[currIndex];
        this.heap[currIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currIndex = leftIndex;
      }
      leftIndex = currIndex * 2;
      rightIndex = currIndex * 2 + 1;
    }

    return returnValue;
  }
}

const heap = new MaxHeap();
heap.push(45);
heap.push(36);
heap.push(54);
heap.push(27);
heap.push(63);
console.log(heap.heap); // [ null, 63, 54, 45, 27, 36 ]

const array = [];
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
array.push(heap.pop());
console.log(array); // [ 63, 54, 45, 36, 27 ] 힙 정렬