우선순위 큐 Priority Queue

우선순위 큐 (Priority Queue)

우선순위 큐는 들어온 순서(FIFO)가 아니라 우선순위가 가장 높은 요소가 먼저 나오는 큐 자료구조입니다.

---

우선순위 큐의 추상 자료형 ADT

• push(x) : 우선순위를 가진 요소 삽입
• pop() : 가장 높은 우선순위 요소 제거 및 반환
• peek() : 가장 높은 우선순위 요소 조회
• size() : 요소 갯수 반환

---

Min Heap

• 부모 노드 ≤ 자식 노드
• 루트 노드에 최소값이 위치
• 최소값을 O(1) 에 조회
• 삽입 / 삭제는 O(log N)

        1
      /   \
     3     5
    / \
   8   10

---

Max Heap

• 부모 노드 ≥ 자식 노드
• 루트 노드에 최대값 위치
• 구현은 Min Heap과 동일하되 비교 연산만 반대

       10
      /  \
     8    5
    / \
   1   3

---

구현 코드

대표적인 우선순위 큐의 자료구조 중 하나인 Min Heap을 구현해보겠습니다.

배열로 구현 시 매 삽입/삭제마다 정렬이 필요하여 O(N log N)
힙 기반 구현은 삽입/삭제가 O(log N)
실전에서는 Heap 기반 구현이 표준

---

class MinHeap {
  #heap;

  constructor() {
    this.#heap = [];
  }

  push(x) {
    this.#heap.push(x);
    this._bubbleUp();
  }

  pop() {
    if (this.size() === 0) throw new Error("MinHeap is Empty");
    if (this.size() === 1) return this.#heap.pop();

    let root = this.peek();

    this.#heap[0] = this.#heap.pop();
    this._bubbleDown();

    return root;
  }

  peek() {
    return this.#heap[0];
  }

  size() {
    return this.#heap.length;
  }

  _bubbleUp() {
    let idx = this.size() - 1;

    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);

      if (this.#heap[parentIdx] <= this.#heap[idx]) break;

      [this.#heap[parentIdx], this.#heap[idx]] = [
        this.#heap[idx],
        this.#heap[parentIdx],
      ];

      idx = parentIdx;
    }
  }

  _bubbleDown() {
    let idx = 0;
    let len = this.size();

    while (true) {
      let left = idx * 2 + 1,
        right = idx * 2 + 2,
        small = idx;

      if (left < len && this.#heap[small] > this.#heap[left]) small = left;
      if (right < len && this.#heap[small] > this.#heap[right]) small = right;
      if (small === idx) break;

      [this.#heap[small], this.#heap[idx]] = [
        this.#heap[idx],
        this.#heap[small],
      ];

      idx = small;
    }
  }
}

---

push

새로운 요소를 힙에 추가한 후,
부모 노드와 비교하며 위로 올립니다. (bubbleUp)

const pq = new MinHeap();

pq.push(5);
pq.push(3);
pq.push(8);
pq.push(1);

// #heap : [1, 3, 8, 5]

---

pop

최소값(루트)을 제거한 후 마지막 요소를 루트로 옮기고 아래로 내립니다. (bubbleDown)

pq.pop(); // 1
pq.pop(); // 3

// #heap : [5, 8]

---

peek

우선순위가 가장 높은 요소(최소값) 를 확인합니다.

pq.peek(); // 5

---

size

힙의 요소 갯수를 확인합니다.

pq.size(); // 2