🎯 Achievement Goals

우선순위 큐(Priority Queue)에 대해서 이해한다.

우선순위 큐(Priority Queue)를 구현하기 위해 필요한 힙(Heap)에 대해서 이해한다.

우선순위 큐(Priority Queue)를 구현할 줄 안다.

우선순위 큐(Priority Queue) ?

일반적인 큐(Queue)는 선입선출(First in-First Out)구조이다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조였다.

하지만 우선순위 큐(Priority Queue)는 들어온 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 것을 말한다.

이러한 우선순위 큐(Priority Queue)를 구현하기 위해서는 우리는 자료구조 힙(Heap)을 사용한다. 그러면 배열이나 연결 리스트가 아닌 왜 힙(Heap)을 사용할까?

보통 배열이나 연결 리스트에서의 삭제는 O(1)의 시간 복잡도를 가지지만, 삽입을 할 경우 O(n)의 시간 복잡도를 가진다. 삽입의 경우 삽입해야 하는 위치를 찾기 위해 모든 인덱스를 탐색하기 때문이다.

힙(Heap)의 경우 삭제나 삽입 과정에서 모두 부모와 자식 간의 비교만 이루어진다. 시간 복잡도는 O(log2n)을 가진다. 힙(Heap)에 대해서 더 자세히 다뤄보자.

힙(Heap) ?

그렇다면 힙(Heap)이 도대체 무엇이길래 우선순위 큐(Priority Queue)는 힙(Heap)으로 구현을 할까?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)의 일종으로 모든 노드에 저장된 값(우선순위)들은 자식 노드들 보다 우선순위가 크거나 같다.

따라서 힙(Heap)은 루트 노드에 우선순위가 높은 데이터를 위치시키는 자료구조이다. 그러므로 힙에서 저장된 값(노드)을 뺄 때마다 우선순위가 높은 데이터 먼저 빠져나온다.

힙(Heap)에는 최대 힙(max heap)과 최소 힙(min heap)이 있다.

최대 힙(max heap)

maxHeap

최대 힙(max heap)이란 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리이다. 즉, 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다.

최소 힙(min heap)

minHeap

최소 힙(min heap)이란 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리이다. 루트 노드로 올라갈수록 값이 작아지는 구조이며, 우선순위 값이 작은 순서대로 우선하게 된다.

최대 힙, 최소 힙 상관없이 루트 노드에는 우선순위가 높은 것이 자리잡게 된다.

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

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  // 항상 최상위 노드가 peek가 된다.
  peek = () => this.heap[0];
}

최소 힙(min heap) 저장 과정

minHeap1

minHeap2

minHeap3

그림과 같이 부모와 비교해가면서 자식이 더 작으면 서로 자리바꿈을 하면 되는 것이다. 만약 부모 노드가 더 작으면 그 자리에서 멈추고 자리는 고정된다. (최대 힙(max heap)은 반대로 생각하면 된다.)

class Heap {
  // 생략

  // 우선순위를 비교하기 위해 key, value로 받는다.
  insert = (key, value) => {
    const node = { key, value };
    this.heap.push(node);
    // 먼저 배열의 가장 끝에 넣어놓고, 다시 min heap의 형태를 갖춘다.
    this.heapifyUp();
  };

  heapifyUp = () => {
    let index = this.heap.length - 1;
    const lastInsertedNode = this.heap[index];

    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      // 부모 노드의 Key 값이 마지막에 삽입된 노드의 키 값 보다 크다면
      // 부모와 자리바꿈을 한다.
      if (this.heap[parentIndex].key > lastInsertedNode.key) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else {
        break;
      }
    }
    // break를 만나서 자신의 자리를 찾은 상황
    // 현재 찾은 자리가 마지막에 들어온 노드가 들어갈 자리이다.
    this.heap[index] = lastInsertedNode;
  };
}

최소 힙(min heap) 삭제 과정

우선순위 큐(Priority Queue)에서 pop은 가장 우선순위가 높은 데이터를 빼낸다는 것을 의미한다.

minHeap5

삭제의 과정은 먼저 루트 노드를 반환(삭제)하고 마지막 노드를 루트 노드자리에 옮긴다.

minHeap6

그 다음 왼쪽 4와 오른쪽 5를 비교해서 우선순위가 더 높은 4와 비교를 진행한다. 이런식으로 계속 진행하면서 최소 힙의 구조를 유지할 때까지 반복한다.

class Heap {
  // 생략

  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0];

    if (count <= 0) {
      return undefined;
    }
    if (count === 1) {
      this.heap = [];
    } else {
      // 2개 이상이면 끝에 있는 노드를 최상위 노드로 만든다.
      this.heap[0] = this.heap.pop();
      // 다시 min heap의 형태를 갖춘다.
      this.heapifyDown();
    }

    return rootNode;
  };

  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.heap[index];

    // 계속해서 left Child가 있을 때 까지 검사한다.
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 왼쪽, 오른쪽 중에 더 작은 노드를 찾는다.
      // rightChild가 있다면 key의 값을 비교해서 더 작은 값을 찾는다.
      // 없다면 leftChild가 더 작은 값을 가지는 인덱스이다.
      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex;

      // 자식 노드의 키 값이 루트 노드보다 작다면 위로 올린다.
      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else {
        break;
      }
    }

    this.heap[index] = rootNode;
  };
}

우선순위 큐(Priority Queue) 구현하기

class PriorityQueue extends Heap {
  constructor() {
    super();
  }

  enqueue = (priority, value) => this.insert(priority, value);
  dequeue = () => this.remove();
  isEmpty = () => this.heap.length <= 0;
}

우선순위 큐(Priority Queue)는 이미 구현한 min heap을 상속해서 세가지 메소드를 구현한다.

enqueue: min heap에 넣기
dequeue: min heap에서 삭제 하기(우선순위가 가장 높은 노드 꺼내기);
isEmpty: heap이 비어있는지 확인하기

참고 자료

자료구조-우선순위 큐
자료구조-힙이란?

← Previous Post Next Post →

자료구조 - Priority Queue

📅 TIL #125