JS로 우선순위 큐 구현하기

우선순위 큐(Priority Queue)

• 일반적인 큐는 선입선출(FIFO) 원칙에 따라 먼저 들어온 데이터가 먼저 처리됨
• 우선순위 큐는 각 데이터들의 정해진 우선순위에 따라 큐에서 처리되어 나감
• 우선순위 큐는 Heap 자료구조의 최소힙(Min Heap) 이용

Heap 자료구조

• 완전 이진 트리의 일종으로, 각 노드의 키 값이 자식의 키 값보다 작지 않거나(=최대 힙), 크지 않은(=최소 힙) 트리

  완전이진트리란?
  루트 노드 → 왼쪽 자식 → 오른쪽 자식 순으로 데이터 삽입되는 트리 형태

• Heap은 항상 루트 노드를 제거하는 식으로 동작

1. 루트 노드 제거
2. 맨 마지막에 들어온 데이터를 루트 노드로 이동
3. 루트 노드를 자식 노드와 비교하며 swap할 위치 찾아 적합한 위치에 해당 데이터 넣기(→ 정렬)

Heap 자료구조를 이용하는 이유

• 배열로 데이터 조회 시 시간 복잡도는 O(N)이지만, Heap 사용 시 O(1)로 낮출 수 있음
• 자료 삽입 및 삭제에도 시간 복잡도는 O(logN)

Heap 자료구조로 우선순위 큐 구현하기

1. heap 배열 만들기 → 생성자 함수에 빈 배열 생성
2. 삽입 메서드(enqueue) → 배열에 데이터 삽입 후 정렬(아래에서 위로) 수행
3. 삭제 메서드(dequeue) → 배열이 비어있지 않은 경우 0인덱스에 있는 데이터 반환 후, 마지막 인덱스에 있는 데이터를 0인덱스에 저장 후 정렬(위에서 아래로)
4. 아래에서 위로 정렬 메서드(heapifyUp)
   • 부모 인덱스의 원소 값과 비교해 본인의 값이 더 작은경우 swap
   • 부모 인덱스의 원소 값보다 본인의 값이 크거나 같을 때까지 수행
5. 위에서 아래로 정렬 메서드(heapifyDown)
   • 본인의 값과 자식 인덱스의 원소 값과 비교
   • 먼저, 왼쪽 자식과 비교 → 본인 값 > 왼쪽 자식 값이면, swap
   • 오른쪽 자식과 비교 → 본인 값 > 오른쪽 자식 값 or 왼쪽 자식 값 > 오른쪽 자식 값이면, swap
   • swap할 데이터가 없을 때까지 반복

인덱스 찾기

• 부모 인덱스 = Math.floor((본인 인덱스-1)/2)
• 왼쪽 자식 인덱스 = 본인 인덱스 * 2 +1
• 오른쪽 자식 인덱스 = 본인 인덱스 * 2 +2

class PriorityQueue {
  constructor() {
    this.heap = []; // 빈 배열 생성
  }

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1; // 왼쪽 자식 인덱스
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2; // 오른쪽 자식 인덱스
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2); // 부모 인덱스

  peek = () => this.heap[0].key; // 루트 노드 반환
  size = () => this.heap.length; // heap 배열 크기 반환
  isEmpty = () => this.heap.length === 0;

  // 원소 삽입
  enqueue = (key, value) => {
    const node = { key, value }; // 우선순위 비교를 위해 노드 형태로 저장
    this.heap.push(node); // 새 원소 마지막 위치에 삽입
    this.heapifyUp(); // 정렬 수행
  };

  // 아래에서 위로 정렬
  heapifyUp = () => {
    let index = this.size() - 1; // 마지막 인덱스
    const lastNode = this.heap[index]; // 마지막 원소

    while (index > 0) {
      const parentIdx = this.getParentIndex(index); // 부모 인덱스 찾기
      // 부모 원소의 종료 시간이 자식 원소 종료시간보다 큰 경우 swap
      if (this.heap[parentIdx].key > lastNode.key) {
        this.heap[index] = this.heap[parentIdx];
        index = parentIdx;
      } else break;
    }
    this.heap[index] = lastNode; // 본인 자리 찾아가기
  };

  // 원소 삭제
  dequeue = () => {
    if (this.isEmpty()) return null; // 비어있는 경우 삭제 불가능

    const rootNode = this.heap[0];
    if (this.heap.length === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop(); // 맨 마지막에 있는 원소 루트로 이동
      this.heapifyDown(); // 정렬 수행
    }
    return rootNode; // 루트 노드 반환
  };

  // 위에서 아래로 정렬
  heapifyDown = () => {
    let index = 0;
    const heapSize = this.size();
    const rootNode = this.heap[index];

    while (this.getLeftChildIndex(index) < heapSize) {
      const leftChildIdx = this.getLeftChildIndex(index); // 왼쪽 자식 인덱스
      const rightChildIdx = this.getRightChildIndex(index); // 오른쪽 자식 인덱스

      // 부모노드가 자식 노드들보다 값이 큰 경우 swap
      // 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 작은 값을 가지는 인덱스와 부모 노드랑 변경
      const smallerChildIndex =
        rightChildIdx < heapSize &&
        this.heap[rightChildIdx].key < this.heap[leftChildIdx].key
          ? rightChildIdx
          : leftChildIdx;

      // 자식 노드 값이 부모 노드보다 작은 경우 swap
      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }
    this.heap[index] = rootNode;
  };
}

---

참고 자료

JavaScript로 Heap | Priority Queue 구현하기
[자료구조] 자바스크립트로 우선순위 큐(Priority Queue) 구현하기
힙 (최소 힙, 최대 힙)