[자료구조] 우선 순위 큐 (Priority Queue)

우선 순위 큐 (Priority Queue)

우선순위 큐 자료구조는 큐(queue) 자료구조의 특징을 활용하되 데이터들간에 우선순위가 존재하는 자료구조이다. 우선순위 큐 자료구조는 이와 같이 하나의 기준을 가지고 데이터가 순서대로 정렬될 수 있기 때문에 이전에 살펴보았던 이진 힙 (Bianry Heap) 자료구조를 통해 쉽게 구현할 수 있다. 우선순위 큐를 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 통해 구현하느냐에 따라서 세부사항은 달라질 수 있겠지만, 우선순위 큐 자료구조는 보통 다음과 같은 특징을 지닌다.

1. 우선순위 큐의 데이터는 Node와 같이 값과 우선순위를 동시에 지닐 수 있는 형태를 지닌다.
2. 우선순위 큐의 데이터들은 우선순위를 기준으로 최소힙-오름차순, 최대힙-내림차순 으로 정렬된다. (가장 앞에 정렬되어 있는 데이터가 우선순위가 가장 높다.)
3. 우선순위 큐는 제일 우선순위가 높은 데이터를 출력하고, 우선순위에 따라서 데이터를 삽입하고 정렬하는 데에 그 의미가 있다.

최소 힙을 통해 우선 순위 큐 구현

이전에 이진 힙 자료구조에서 최대 힙을 구현해보았으니 이번에 우선순위 큐를 구현하는데에는 최소 힙 형태를 통해 구현해보도록 하자. (규칙만 지켜준다면 최대 힙-최소 힙의 종류는 상관이 없다.) 먼저 최소 힙을 구현하기 전에, 기본 자료형은 value와 priority 두 가지 값을 가지고 있는 Node형태를 기준으로 한다.

// 기본 자료형
class Node {
	constructor(value, priority) {
    	this.value = value;
      	this.priority = priority
    }
}

이 Node 자료형을 기준으로 여러 가지 값과 우선 순위를 가진 데이터를 생성하고, 이를 담을 수 있는 우선순위 큐를 구현해보도록 하자. 우선순위 큐는 다음과 같은 프로퍼티를 지녀야 한다.

1. queue: 데이터를 최소 힙 형태로 저장할 이진 힙 자료구조이다. 이전과 동일하게 배열을 통해서 구현한다.

class PriorityQueue {
  constructor() {
  	this.queue = [];
  }
}


const PQ = new PriorityQueue ();

// 이전 최대 힙 자료구조와 마찬가지로 배열을 선언해주는 것만으로 충분하다.
// 자료의 삽입과 제거는 메소드가 담당하게 된다.

우선순위 큐 메소드

손쉽게 우선순위 큐 자료구조를 구현했으니, 이를 실질적으로 사용하게 끔 만들어줄 우선순위 큐 메소드들을 살펴보고 구현해보도록 하자. 주의해야할 점은 이번 우선순위 큐를 구현하는데에는 최소 힙 자료구조를 사용할 것이라는 점이다. 최대 힙 자료구조에서 insert, remove이라는 메소드를 사용했지만 큐 자료구조에 더 걸맞게 비슷하지만 enqueue, dequeue 로 명칭을 바꾸어 사용한다. 한 가지 더 기억해야할 점으로, 우선순위 큐 자료구조이기 때문에 자료형의 데이터 즉, 값은 중요하지 않다. 정렬의 기준이 되는 것은 반드시 우선순위 값이다.

enqueue(value, priority)

enqueue 메소드는 우선순위 큐에 새로운 Node를 추가한다. 이때 중요한 점은 정렬의 기준이 되는 것은 자료형의 우선순위 값이라는 점이다. 최소 힙으로 자료를 삽입할 것이기 때문에 반드시 부모의 우선순위가 자식의 우선순위를 앞서야(값이 작아야) 한다. enqueue 메소드는 다음과 같은 규칙을 지닌다.

1. 우선순위 큐의 끝에 새로운 데이터를 삽입한다.
2. 현재 삽입된 데이터의 부모 index를 취해, 해당 부모의 우선순위와 본인의 우선순위를 비교한다.
3. 만약 값이 올바르다면 해당 위치에 그대로 두고, 그렇지 않다면 부모와의 위치를 교환한다.
4. 값이 제 위치를 찾을 때까지 비교-교환 과정을 계속한다.

enqueue(value, priority) {
	const newNode = new Node(value, priority);
  	this.queue.push(newNode);
  	// 새로운 Node를 생성해서 큐에 삽입한다.
  
  	if(!this.queue.length) return this.queue;
  	// 만약 이전의 큐가 빈큐였다면 그대로 반환한다.
    
  	let curIdx = this.queue.length - 1;
  	let parentIdx = Math.floor((curIdx - 1) / 2);
  	let curPriority = this.queue[curIdx].priority;
  	// 현재 idx, 부모의 idx, 현재 데이터의 우선순위를 선언한다.	
  
	while(curPiroirty < this.queue[parentIdx]){
      // 현재 우선순위가 부모의 우선순위보다 작을 경우 (즉, 우선할경우)
        [this.queue[curIdx], this.queue[parentIdx]] = [
        this.queue[parentIdx],this.queue[curIdx]];
      // 현재 Node와 부모 Node의 위치를 바꾼다.	
      
      curIdx = parentIdx;
      // 교체되었다면,
      // 현재 idx를 부모의 idx로 교체한다.
      parentIdx = Math.floor((curIdx - 1) / 2);
      // 부모의 idx를 새롭게 교체한다.
      
      if (parentIdx < 0) break;
      // 만약 부모의 idx가 0보다 작아 연산을 실행할 수 없다면 반복을 종료한다.
    }
	
	return this.queue;
}

PQ.enqueue("First", 20);
PQ.enqueue("Second", 10);
PQ.enqueue("Third", 30);

// {queue: [
// 	{value: "Second", priority: 10}, 
// 	{value: "First", prioirty: 20}, 
// 	{value: "Thirds", prioirty: 30}
// ]}

dequeue()

dequeue 메소드는 이진 힙의 remove 메소드와 같이 실행하게 되면 힙에서 root에 위치하고 있는 값을 빼내어서 출력한다. 우리가 구현하고 있는 우선순위 큐에서는 최소의 우선순위를 가진 Node를 빼내어서 출력한다. dequeue 메소드는 다음과 같은 과정을 거친다.

1. 큐에서 Root 값을 뽑아낸다.
2. 가장 마지막에 추가된 값을 새로운 Root로 할당한다.
3. 새로운 Root와 그의 자식 node들과 값을 비교한다.
4. 만약 자식들 중 하나 라도 Root보다 우선순위가 작다면 서로 위치를 교체한다.
5. 자리가 재조정될 때까지 3-4의 과정을 반복한다.

dequeue() {
  	// 만약 빈 큐라면, null을 반환한다.
  	if(!this.queue.length) return null;
  	// 값이 딱 하나라면, 그 값을 pop 하고 반환한다.
  	if(this.queue.length === 1) return this.queue.pop();
  	
	const result = this.queue[0];
  	this.queue[0] = this.queue.pop();
	// root의 값을 저장하고, 제일 끝의 값으로 교체한뒤 끝 값을 제거한다.
  
	let curIdx = 0;
    let leftChild = 1;
    let rightChild = 2;
  	// idx 선언

  
    while (
      // 만약 두 자식들의 우선순위들 중 하나라도 부모의 우선순위보다 높다면
      this.queue[curIdx].priority > this.queue[leftChild].priority ||
      this.queue[curIdx].priority > this.queue[rightChild].priority
    ) {
      if (
        // 그 중에서도 왼쪽, 오른쪽 자식들의 우선순위를 비교
        this.queue[leftChild].priority < this.queue[rightChild].priority
      ) {
		[this.queue[curIdx], this.queue[leftChild]] = 
        [this.queue[leftChild], this.queue[curIdx]];
        curIdx = leftChild;
      } else {
        [this.queue[curIdx], this.queue[rightChild]] = 
        [this.queue[rightChild], this.queue[curIdx]];
        curIdx = rightChild;
      }
      // 해당 되는 자식과 위치를 교체하고, idx도 교체한다.

      leftChild = curIdx * 2 + 1;
      rightChild = curIdx * 2 + 2;
      // 새로운 idx 계산

      if (!this.queue[leftChild]) break;
      // leftChild 가 rightChild보다 앞서기 때문에
      // leftChild의 값이 존재하지 않으면 탐색이 끝이난 것이다.

      if (!this.queue[rightChild]) rightChild = leftChild;

      // 미처 탐색하지 못한 leftChild가 존재할 수 있다.
    }
  	
  return result;
}


PQ.dequeue();
PQ.dequeue();
PQ.dequeue();

// 	{value: "Second", priority: 10}
// 	{value: "First", prioirty: 20}
// 	{value: "Thirds", prioirty: 30}