힙

이진 트리 형태를 가지며 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 정렬되는 특징이 있다. 완전 이진 트리의 높이가 $\log n$이기 때문에 힙의 요소 삽입, 삭제 알고리즘은 $O(\log n)$ 시간복잡도를 가진다.

삽입

요소가 추가될 때에는 트리의 가장 마지막 정점에 위치하고, 추가 후 부모 정점보다 우선 순위가 높다면 부모 정점과 순서를 바꾼다. 이 과정을 반복하여 가장 우선 순위가 높은 정점이 루트가 된다.

삭제

요소의 제거는 루트 정점만 가능하다. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다. 루트 정점의 두 자식 중 더 우선 순위가 높은 정점과 바꾸며 두 자식 정점의 우선 순위가 더 낮을 때까지 반복한다.

구현

최대 힙(Max Heap)

최대 힙이란, 부모 노드가 자식 노드보다 같거나 큰 것이다.

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 && this.heap[parentIndex] < value) {
      this.heap[currentIndex] = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }
  
  pop() {
    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]) {
        const temp = this.heap[currentIndex];
        if (this.heap[leftIndex] < this.heap[rightIndex]) {
          this.heap[currentIndex] = this.heap[rightIndex];
          this.heap[rightIndex] = temp;
          currentIndex = rightIndex;
        } else {
          this.heap[currentIndex] = this.heap[leftIndex];
          this.heap[leftIndex] = temp;
          currentIndex = leftIndex;
        }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
  }
}

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

요소를 삽입할 때에는 우선 최하위 노드에 요소가 추가된다. 그리고 부모 노드와 우선 순위를 비교하면서 상위로 이동한다. 부모 인덱스(parentIndex)는 자식을 최대 두 개 씩 갖고 있으므로 현재 인덱스(currentIndex)에서 나누기 2를 해주어야 한다. 이어서 반복문을 돌려 부모 노드보다 현재 자신의 노드가 더 큰 경우에 값을 서로 바꾸어 주면 된다. 이 시점의 현재 노드는 부모 노드의 위치로 이동했기 때문에 currentIndex를 parentIndex로 바꿔주어야 한다.

요소를 삭제할 때에는 우선 순위인 루트 노드를 삭제한 후, 마지막 요소를 루트 정점에 놓는다. 이후에 좌/우측 자식노드와 우선 순위를 비교하면서 재정렬을 한다. 반복문이 실행하는 시점에서 우측 자식 노드의 우선 순위가 좌측 자식노드보다 더 높다면 우측 자식 노드와 현재 노드를 바꾼다. 반대의 경우에는 좌측과 바꾼다. 이를 반복하면서 좌/우측 자식 노드의 우선 순위보다 낮아지면 종료한다.

최소 힙(Min Heap)

최소 힙이란, 부모 노드가 자식 노드보다 작거나 큰 것이다. 즉, 최대 힙은 값이 제일 큰 순으로 우선 순위를 매겼다면 최소 힙은 값이 작은 순으로 우선 순위를 매기는 것이다. 따라서 최소 힙의 구현은 최대 힙에서 대소 관계만 반대로 해주면 된다.

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 && this.heap[parentIndex] > value) {
      this.heap[currentIndex] = this.heap[parentIndex];
      this.heap[parentIndex] = value;
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }
  
  pop() {
    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]) {
      const temp = this.heap[currentIndex];
        if (this.heap[leftIndex] > this.heap[rightIndex]) {
          this.heap[currentIndex] = this.heap[rightIndex];
          this.heap[rightIndex] = temp;
          currentIndex = rightIndex;
        } else {
          this.heap[currentIndex] = this.heap[leftIndex];
          this.heap[leftIndex] = temp;
          currentIndex = leftIndex;
        }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
  }
}

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

---

만약 제가 고려하지 못한 부분이 있다면 알려주세요, 감사합니다 :)