[JS] 최소 힙

백준 1927. 최소 힙

힙 (Heap)

힙은 이진 트리의 일종으로, 부모 노드와 자식 노드 간의 특정 관계를 유지하는 자료 구조이다. 힙은 완전 이진 트리 구조를 가지는데, 이는 트리가 항상 왼쪽부터 순차적으로 채워진다는 의미이다. 그래서 트리를 배열로 쉽게 표현하고 관리할 수 있다.

힙에는 두 가지 종류가 있다. 최소 힙과 최대 힙이다.

최소 힙 (Min Heap)

최소 힙은 부모 노드가 자식 노드보다 항상 작은 값을 가지는 완전 이진 트리이다. 최상단의 루트 노드는 항상 트리에서 가장 작은 값을 가진다. 새로운 요소가 추가되면 upheap 과정을 수행하고, 루트에 있던 최솟값이 삭제되면 가장 마지막에 있던 요소를 맨 앞으로 이동시킨 후 downheap 과정을 수행하여 힙의 규칙을 유지한다.

최대 힙 (Max Heap)

최대 힙은 최소 힙과 반대로, 부모 노드가 자식 노드보다 항상 큰 값을 가지는 완전 이진 트리이다. 최상단의 루트 노드는 트리에서 가장 큰 값을 가진다. 최소 힙과 유사하게 upheap과 downheap을 통해 힙의 규칙을 유지한다.

upheap과 downheap 과정

• upheap은 새로 삽입된 요소를 적절한 위치로 올려 부모가 자식보다 항상 작은 값(최소 힙의 경우)을 유지하도록 하는 과정이다. 이 과정에 따라, 힙에서 삽입과 삭제의 시간 복잡도는 최악의 경우 O(log N)이다. logN은 트리의 높이와 같다.
• downheap은 루트 노드에서 시작하여 자식 노드와 비교해 적절한 위치로 내려가는 과정이다. 루트에서 가장 작은 값을 추출하고 나면 맨 마지막에 있던 값이 루트로 올라가는데, 이때 부모가 자식보다 작은 값(최소 힙의 경우)을 항상 유지하기 위해 사용된다. 시간복잡도는 upheap과 동일하게 O(log N)이다.

---

JavaScript는 기본적으로 힙 자료 구조를 지원하지 않으므로 직접 구현해야 했다. 배열의 첫 번째 요소(0번 인덱스)가 항상 가장 작은 값을 가지도록 유지한다.

// 최소 힙: 부모 노드가 자식 노드보다 항상 작은 완전 이진 트리
// 힙의 루트 노드(0번 인덱스)가 항상 가장 작은 값을 가지도록 유지한다.
// insert: 새로운 요소를 힙에 추가하고 upheap 과정을 통해 올바른 위치로 이동
// pop: 루트 노드를 pop하고 마지막 노드를 루트로 이동한 뒤 downheap 과정을 통해 올바른 위치로 이동

class MinHeap {
  constructor() {
    this.heap = [];
  }
  swap(index1, index2) {
    // 구조 분해 할당 사용해 swap
    [this.heap[index1], this.heap[index2]] = [
      this.heap[index2],
      this.heap[index1],
    ];
  }

  upheap(index) {
    const x = this.heap[index];
    while (index > 0) {
      let upIndex = Math.ceil(index / 2) - 1;
      if (x < this.heap[upIndex]) this.swap(index, upIndex);
      else break;
      index = upIndex;
    }
  }

  downheap(index) {
    let n = this.heap[index];
    // 왼쪽 자식 없을 때까지 진행
    while (index * 2 + 1 <= this.heap.length - 1) {
      let downIndex = index * 2 + 1;
      // 오른쪽 자식이 있다면 둘 중 더 작은 요소를 골라
      if (downIndex + 1 <= this.heap.length - 1) {
        if (this.heap[downIndex] > this.heap[downIndex + 1]) downIndex++;
      }
      // 부모보다 작다면 swap
      if (n > this.heap[downIndex]) this.swap(index, downIndex);
      else break;
      index = downIndex;
    }
  }

  insert(x) {
    this.heap.push(x);
    let index = this.heap.length - 1;
    this.upheap(index);
  }

  pop() {
    if (this.heap.length == 0) return 0;
    // 첫 요소(root)와 마지막 요소의 자리를 바꿈
    this.swap(0, this.heap.length - 1);
    // 마지막 요소를 pop
    let r = this.heap.pop();
    this.downheap(0);
    return r;
  }
}

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];
let output = []; // 결과 출력을 위한 배열

readline.on("line", (line) => {
  if (line.trim() === "") {
    readline.close();
  } else {
    input.push(line);
  }
});

readline.on("close", () => {
  const N = input[0];
  const minHeap = new MinHeap();
  for (let i = 1; i <= N; i++) {
    if (input[i] == 0) {
      output.push(minHeap.pop());
    } else {
      minHeap.insert(parseInt(input[i]));
    }
  }
  console.log(output.join("\n"));
  process.exit();
});

---

우선순위 큐 (Priority Queue)

우선순위에 따라 요소가 정렬되는 데이터 구조이다. 최댓값이나 최솟값을 빠르게 꺼내야 할 때 유용하다.

+)
[Python] 이중 우선순위 큐