[DA] Heap

Priority Queue

FIFO 구조가 아닌 우선 순위가 높은 요소가 먼저 나가는 Queue

Heap 으로 구현 적합

Heap

이진 트리 형태

우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬

Max Heap(루트가 가장 큰 값), Min Heap(루트가 가장 작은 값)

Heap 요소 추가

1. 요소가 추가될 때는 트리의 가장 마지막 정점에 위치
2. 추가 후 부모 정점보다 우선순위가 높다면 부모정점과 순서를 교체

Heap 요소 제거

1. 요소 제거는 루트 정점만 가능
2. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치
3. 루트 정점의 두 자식 정점 중 더 우선 순위가 높은 정점과 교체
4. 두 자식 정점이 우선 순위가 더 낮을 때 까지 반복

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

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

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

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

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

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;

    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
    ) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }

      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }

    return returnValue;
  }
}