[Algorithm] 최소 힙(Heap)으로 우선순위 큐 구현하기

힙의 특징

---

최단 경로를 찾을 때 널리 사용하는 다익스트라 알고리즘은, 탐색 큐의 자료구조가 전체 성능에 결정적인 영향을 미친다. 때문에 추가/삭제를 빠르게 수행할 수 있는 우선순위 큐를 주로 사용한다.

 

우선순위 큐는 일반 큐와 비슷하지만, 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 출력된다는 점이 다르다. 우선순위 큐는 크게 배열, 연결리스트, 힙 이렇게 세 가지 방법으로 구현할 수 있다. 그중 완전 이진 트리 구조를 갖는 힙으로 구현하면 추가/제거의 효율성이 크게 향상된다.

 

구현 방법	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(log n)	O(log n)

 

이진 트리는 각 부모 노드가 왼쪽/오른쪽 최대 2개의 자식 노드를 가질 수 있는 구조를 가리킨다. 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨을 완전히 채워진 상태로 유지해야 한다. 때문에 자식 노드를 추가할 땐 왼쪽부터 차례대로 채워야 한다. 아래 이미지 왼쪽에 있는 트리는 31번 노드의 자식을 오른쪽부터 채웠기 때문에 완전 이진 트리가 아니다.

 

 

힙은 크게 최대 힙(Max Heap), 최소 힙(Min Heap)으로 분류된다. 최대 힙은 부모 노드가 항상 자식 보다 크거나 같고, 최소 힙은 부모 노드가 항상 자식보다 작거나 같다. 다익스트라 알고리즘은 거리 값이 낮은 노드에 높은 우선순위를 부여하므로, 루트 노드가 가장 짧은 거리 값(우선순위가 높은)을 갖는 최소 힙을 사용하는 것이 적절하다.

 

 

 

배열로 표현하는 최소 힙

---

 

위에서 살펴본 완전 이진 트리 특성을 이용하면 각 노드의 인덱스를 아래 공식으로 계산할 수 있다.

 

• 왼쪽 자식 노드 인덱스 : 부모 노드 인덱스 × 2 + 1
• 오른쪽 자식 노드 인덱스 : 부모 노드 인덱스 × 2 + 2
• 부모 노드 인덱스 : (자식 노드 인덱스 - 1) / 2

 

예를들어 부모 노드의 인덱스가 2라면 왼쪽 자식 인덱스는 5, 오른쪽 자식 인덱스는 6이 된다. 이처럼 한 노드의 인덱스만 알면 해당 노드의 부모/자식 노드의 인덱스도 확인할 수 있어서 배열 구조로도 트리를 표현할 수 있다.

 

 

Enqueue

---

노드 추가는 최소 힙 속성(부모 노드 ≤ 자식 노드)을 만족할 때까지 부모 노드와 비교하며 위치를 교환하는 방식으로 이뤄진다. 노드 위치를 교환하는 과정은 heapify-up이라고 부른다. heapify-up은 최악의 경우 트리 높이 만큼 반복되고, 트리 높이는 $\log_{2}V$이므로 노드 추가의 시간 복잡도 역시 $\log_{2}V$를 갖는다.

 

1. 새로운 노드를 힙의 가장 마지막에 추가한다 — heap.push(node)
2. 새로 추가한 노드를 부모 노드와 비교하여 더 작다면 위치를 바꾼다 — heapify-up
3. 새로 추가한 노드가 부모 노드보다 크거나, 루트에 도달할 때까지 이 과정을 반복한다

 

💡 트리에서 높이는 루트 노드(깊이 0)에서 리프 노드까지의 거리를 의미한다. 완전 이진 트리에서 각 레벨의 노드 수는 이전 레벨 노드 수의 2배로 증가한다. 따라서 높이가 $h$인 완전 이진 트리는 최소 $2^{h}$에서 최대 $2^{h+1}-1$개의 노드를 가질 수 있다. 예를 들어, 높이가 2인 트리는 최대 $2^{2+1}-1=7$개의 노드를 가질 수 있다. 즉, $V$개의 노드를 가진 완전 이진 트리의 높이는 $\log_{2}V$로 계산할 수 있다.

 

 

 

Dequeue

---

노드 제거 역시 힙 속성을 만족할 때까지 자식 노드와 비교하며 위치를 교환하는 방식으로 이뤄진다. 노드 위치를 교환하는 과정은 heapify-down이라고 부른다. heapify-down은 heapify-up과 마찬가지로 최악의 경우 트리 높이 만큼 반복되고, 트리 높이는 $\log_{2}V$이므로 노드 제거의 시간 복잡도는 $\log_{2}V$를 갖는다.

 

1. 힙의 루트 노드를 제거하고, 마지막 노드를 루트로 이동 시킨다 — heap[0]=heap.pop()
2. 루트로 이동한 노드보다 자식 노드가 더 작다면 위치를 바꾼다 — heapify-down
3. 루트로 이동한 노드가 자식 노드보다 작거나, 리프 노드에 도달할 때까지 이 과정을 반복한다

 

💡 배열 마지막 요소로 삭제한 루트 노드 자리를 채우는 이유: 배열 마지막 요소를 꺼내는 작업은 $O(1)$ 상수 시간 복잡도를 갖기 때문. 힙에서 루트 노드를 삭제하면 힙 구조를 유지하기 위해 다른 노드로 그 자리를 채워야 한다. 배열 마지막 요소를 사용하면 추가적인 요소 이동 없이 빠르게 루트의 빈 자리를 채울 수 있어, 힙의 재정렬을 시작하는 가장 효율적인 방법이다.

 

 

 

코드 구현

---

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

  // 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1
  getLeftChildIndex(parentIdx) {
    return 2 * parentIdx + 1;
  }

  // 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 2
  getRightChildIndex(parentIdx) {
    return 2 * parentIdx + 2;
  }

  // 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2
  getParentIndex(childIdx) {
    return Math.floor((childIdx - 1) / 2);
  }

  // 주어진 인덱스에 위치한 (부모)노드에 왼쪽 자식 노드가 있는지 확인
  // 왼쪽 자식 노드의 인덱스가 전체 노드 갯수보다 작을 경우에만 자식 노드가 존재한다고 간주
  hasLeftChild(idx) {
    return this.getLeftChildIndex(idx) < this.heap.length;
  }

  // Checks if a right child exists for the given idx
  hasRightChild(idx) {
    return this.getRightChildIndex(idx) < this.heap.length;
  }

  // Checks if a parent exists for the given idx
  hasParent(idx) {
    return this.getParentIndex(idx) >= 0;
  }

  // Retrieves the left child's value for the given idx
  leftChild(idx) {
    return this.heap[this.getLeftChildIndex(idx)];
  }

  // Retrieves the right child's value for the given idx
  rightChild(idx) {
    return this.heap[this.getRightChildIndex(idx)];
  }

  // Retrieves the parent's value for the given idx
  parent(idx) {
    return this.heap[this.getParentIndex(idx)];
  }

  // Swaps the elements at the two given indexes
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  // Returns the minimum element without removing it
  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }

  // Removes and returns the minimum element from the heap
  remove() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const rootNode = this.heap[0];
    this.heap[0] = this.heap.pop(); // 가장 마지막에 있는 노드를 루트 노드로 만들고
    this.heapifyDown(); // 다시 Min Heap 속성을 갖도록 조정
    return rootNode;
  }

  // Adds a new element to the heap
  add(priority, value) {
    this.heap.push({ priority, value: !value ? priority : value });
    this.heapifyUp();
  }

  // Moves the last element up to its correct position in the heap
  heapifyUp() {
    let idx = this.heap.length - 1;

    // 부모 노드가 없으면 옵셔널 체이닝으로 인해 undefined 반환 -> while문 조건 통과 X
    while (this.parent(idx)?.priority > this.heap[idx].priority) {
      const parentIdx = this.getParentIndex(idx);

      this.swap(parentIdx, idx);
      idx = parentIdx;
    }
  }

  // Moves the root element down to its correct position in the heap
  heapifyDown() {
    let idx = 0;

    while (this.hasLeftChild(idx)) {
      let smallestIdx = this.getLeftChildIndex(idx);
      // 오른쪽 자식 노드가 없으면 옵셔널 체이닝으로 인해 undefined 반환 -> while문 조건 통과 X
      if (this.rightChild(idx)?.priority < this.leftChild(idx).priority) {
        // 왼쪽/오른쪽 자식 중 우선순위가 더 높은(priority 값이 더 작은) 노드 선택
        smallestIdx = this.getRightChildIndex(idx);
      }
      // 부모 노드가 자식 노드보다 더 작으면 heapifyDown 중지
      if (this.heap[idx].priority <= this.heap[smallestIdx].priority) break;

      this.swap(idx, smallestIdx);
      idx = smallestIdx;
    }
  }

  // Prints all elements in the heap
  printHeap(property = 'priority') {
    console.log(this.heap.map((element) => element[property]).join(' '));
  }
}

export default MinHeap;

 

기본 구조

노드의 인덱스를 계산하는 로직 등은 자주 사용하므로 메서드로 미리 구현해둔다. has*Child 같은 메서드는 주어진 인덱스에 위치한 노드에 왼쪽/오른쪽 자식 노드가 있는지 확인한다.

 

주의할 점은 계산한 자식 노드의 인덱스가 전체 노드 갯수(heap.length)보다 작을 경우에만 존재한다고 간주해야 한다. 예를 들어 트리에 루트 노드 1개밖에 없다면 배열 길이는 1이 된다. 이때 루트 노드에 대한 왼쪽/오른쪽 자식 노드의 인덱스는 각각 1, 2로 배열 길이와 같거나 크기 때문에 자식 노드가 없는 걸로 처리해야 한다.

class MinHeap {
  constructor() {
    this.heap = []; // [{ priority: number, value: any }, ...]
  }

  // 유틸리티 함수
  getLeftChildIndex(parentIdx) {
    return 2 * parentIdx + 1;
  }
  getRightChildIndex(parentIdx) {
    return 2 * parentIdx + 2;
  }
  getParentIndex(childIdx) {
    return Math.floor((childIdx - 1) / 2);
  }

  hasLeftChild(idx) {
    return this.getLeftChildIndex(idx) < this.heap.length;
  }
  hasRightChild(idx) {
    return this.getRightChildIndex(idx) < this.heap.length;
  }
  hasParent(idx) {
    return this.getParentIndex(idx) >= 0;
  }

  leftChild(idx) {
    return this.heap[this.getLeftChildIndex(idx)];
  }
  rightChild(idx) {
    return this.heap[this.getRightChildIndex(idx)];
  }
  parent(idx) {
    return this.heap[this.getParentIndex(idx)];
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  // ...
}

 

추가 (Enqueue)

새로운 노드를 받아 heap 배열 가장 끝에 추가한다. 그 후 heapifyUp 메서드를 호출해서 힙 속성을 만족할 때까지 부모 노드와 비교하며 위치를 교환한다.

class MinHeap {
  // ...

  add(priority, value) {
    this.heap.push({ priority, value: !value ? priority : value });
    this.heapifyUp();
  }

  heapifyUp() {
    let idx = this.heap.length - 1;

    // 부모 노드가 없으면 옵셔널 체이닝으로 인해 undefined 반환 -> while문 조건 통과 X
    while (this.parent(idx)?.priority > this.heap[idx].priority) {
      const parentIdx = this.getParentIndex(idx);
      this.swap(parentIdx, idx);
      idx = parentIdx;
    }
  }
}

 

삭제 (Dequeue)

remove 메서드를 호출하면 트리에서 우선순위가 가장 높은 루트 노드를 임시 저장하고, heap 배열 가장 마지막 노드를 루트 노드로 변경한다. 그 후 다시 힙 속성을 유지하기 위해 heapifyDown 메서드를 호출한 후 임시 저장했던 루트 노드를 반환한다. heapifyDown은 노드 추가와 반대로 자식 노드와 비교하며 위치를 교환한다. 자식 노드가 2개 있다면 둘 중 우선순위가 높은(priority 값이 작은) 노드를 선택해서 비교한다.

class MinHeap {
  // ...

  remove() {
    if (this.heap.length === 0) return null; // 힙에 노드가 없을 때
    if (this.heap.length === 1) return this.heap.pop(); // 힙에 루트 노드만 있을 때
    const rootNode = this.heap[0]; // 현재 루트 노드 임시 저장
    this.heap[0] = this.heap.pop(); // 가장 마지막에 있는 노드를 루트 노드로 만들고
    this.heapifyDown(); // 다시 Min Heap 속성을 갖도록 조정
    return rootNode; // 임시 저장한 루트 노드 반환
  }

  heapifyDown() {
    let idx = 0;

    while (this.hasLeftChild(idx)) {
      let smallestIdx = this.getLeftChildIndex(idx);
      // 오른쪽 자식 노드가 없으면 옵셔널 체이닝으로 인해 undefined 반환 -> while문 조건 통과 X
      if (this.rightChild(idx)?.priority < this.leftChild(idx).priority) {
        // 왼쪽/오른쪽 자식 중 우선순위가 더 높은(priority 값이 더 작은) 노드 선택
        smallestIdx = this.getRightChildIndex(idx);
      }
      // 부모 노드가 자식 노드보다 더 작으면 heapifyDown 중지
      if (this.heap[idx].priority <= this.heap[smallestIdx].priority) break;

      this.swap(idx, smallestIdx);
      idx = smallestIdx;
    }
  }
}

 

디버깅 메서드

최소 힙을 사용할 때 자주 사용하는 디버깅용 메서드를 추가한다. 읽기전용 메서드 peek은 우선순위가 가장 높은 노드 정보를 반환한다. 최소 힙에선 항상 루트노드의 우선순위가 가장 높으므로 $O(1)$ 상수 시간으로 수행할 수 있다.

class MinHeap {
  // ...

  peek() {
    return this.heap.length === 0 ? null : this.heap[0];
  }

  printHeap(property = 'priority') {
    console.log(this.heap.map((element) => element[property]).join(' '));
  }
}

export default MinHeap;

 

• peek: 힙 상태 변경 없이 현재 루트 노드(다음에 반환될 우선순위가 가장 높은 노드)의 정보만 반환
• printHeap : 현재 힙에 저장된 모든 노드를 콘솔로 출력

 

우선순위 큐

MinHeap 클래스를 확장해서 우선순위 큐 기능에 특화된 여러 메서드를 추가한다. 참고로 서브 클래스의 생성자(constructor)를 생략하면 내부적으로 부모 클래스의 생성자 함수를 호출한다(super()). 부모/서브 클래스 생성자가 받는 파라미터가 동일하거나 없다면 생략해도 무방하다.

class PriorityQueue extends MinHeap {
  get size() {
    return this.heap.length;
  }
  get isEmpty() {
    return this.size === 0;
  }

  enqueue(priority, value) {
    this.add(priority, value);
  }
  dequeue() {
    return this.remove();
  }

  clear() {
    this.heap = [];
  }
  contains(value) {
    return this.heap.some((element) => element.value === value);
  }

  // ...
}

 

 

레퍼런스

---

JavaScript로 Heap | Priority Queue 구현하기 | jun-choi-4928

Min Heap in JavaScript | GeeksforGeeks

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요