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

  목  차

• 우선순위 큐
• 최소 힙
  • 시간 복잡도
  • 작동 원리
• 구현 코드

 

 

---

 

  우선순위 큐

 

우선순위 큐(Priority Queue)는 말 그대로 우선순위를 가진 요소들을 저장하는 자료구조이다. 우선순위가 가장 높은 요소를 먼저 꺼낼 수 있게 한다. 대표적으로 최소 힙, 최대 힙이 있다.

 

 

---

 

  최소 힙

 

다익스트라 알고리즘(Dijkstra Algorithm)을 학습하기 전에 우선순위 큐를 배우고 그중에서 최소 힙을 배우기에 이 번에는 최소 힙만 다룰 예정이다.

 

 

  시간 복잡도

 

우선순위 큐를 구현하는 방법에는 여러 가지 있지만, 힙(Heap) 자료구조를 사용하는 것이 가장 효율적이고 우선순위가 가장 높은 데이터를 꺼내는데 O(log N) 만큼 걸린다.

 

 

  작동 원리

 

1. 삽입(Insert): 새로운 요소는 항상 배열의 마지막에 들어간다(push). 그 후 부모 노드와 비교하여 힙의 성질을 만족할 때까지 위로 올라간다. 

 

배열을 기준으로 인덱스가 n인 노드의 자식 인덱스는 2 * n 그리고 2 * n + 1 이다.

반대로 n의 부모 노드는 n / 2(정수 나눗셈)이다.

 

인덱싱을 0부터 할 경우에는 + 1을 해주면 된다. 부모는 (n - 1) / 2(정수 나눗셈)이다.

 

 

결과적으로 queue[queue.length - 1] 부터 시작해서 해당 요소와 부모 요소를 비교해서 해당 요소가 더 작다면 자리를 바꿔주면 된다.

 

 

2. 삭제(Delete): 가장 앞에 있는, 즉 가장 우선순위가 높은 요소를 삭제한다. 삭제 후, 트리의 마지막 요소를 루트(가장 앞)로 옮기고, 자식 노드와 비교하며 힙의 성질을 만족할 때까지 아래로 내려간다.

 

 

예시로 queue = [1, 3, 4]가 있다고 해보자.

여기서 1을 삽입하면 queue[3] 에 1이 들어간다. (현재 queue = [1, 3, 4, 1]);

그리고 그 부모 노드와 비교를 한다. [3]의 부모 노드는 [1]이다. 

부모 노드는 3, 방금 삽입한 노드는 1이므로 자리를 바꾼다. 

그럼 결과적으로 [1, 1, 4, 3]이 된다.

 

삭제를 해보자, 1을 뺀다.

그리고 마지막 노드를 앞으로 가져온다. (현재 queue = [3, 1, 4])

(1을 삭제할 때는 논리적 삭제를 한다. 이유는 shift를 하게 되면 요소를 빼버리게 되고, 모든 인덱스를 당겨오기 때문에 비효율 적이다.)

그리고 그 자식 노드와 비교를 한다. 2 * 0 + 1(왼쪽 자식) 그리고 2 * 0 + 2(오른쪽 자식)

3과 1, 3과 4를 비교한다. 그리고 더 작은 것과 자리를 바꾼다.

결과적으로 [1, 3, 4]가 된다.

 

 

---

 

  구현 코드

 

 

이 코드는 다익스트라 알고리즘(Dijkstra Algorithm)을 위해서 만든 최소 힙(Min Heap)이다.

 

그래서 클래스 외부에는 graph 라는 객체 배열의 형태는 아래와 같다.

to는 연결된 노드이고, dist는 연결된 노드로 가기 위한 가중치(weight(거리))이다.

0을 사용하지 않기 위해서 graph[0]은 비어두었다.

 

const graph = [
	[],  // 사용 안 함.
	[
		{to: 2, dist: 5},
		{to: 3, dist: 4}
	],
	[
		{to: 1, dist: 5},
		{to: 6, dist: 11},
		{to: 3, dist: 5}
	],
	[
		{to: 1, dist: 4},
		{to: 2, dist: 5},
		{to: 4, dist: 8},
		{to: 5, dist: 5}
	],
	[
		{to: 3, dist: 8},
		{to: 5, dist: 6},
		{to: 6, dist: 3}
	],
	[
		{to: 3, dist: 5},
		{to: 4, dist: 6},
		{to: 6, dist: 9}
	],
	[
		{to: 2, dist: 11},
		{to: 4, dist: 3},
		{to: 5, dist: 9},
	]
]

 

class MinHeap {
	
	constructor(seedData){
		this.queue = [seedData]
	}

	insert(object){
		this.queue.push(object);
		
		let lastIdx = this.queue.length - 1;

  // 삽입 후 정렬
		while(
			lastIdx > 0 && this.queue[lastIdx].dist < 
			this.queue[Math.floor((lastIdx - 1) / 2)].dist
		){
			let temp = this.queue[lastIdx];
			const parentIdx = Math.floor((lastIdx - 1) / 2);
		
			this.queue[lastIdx] = this.queue[parentIdx];
			this.queue[parentIdx] = temp;
	
			lastIdx = parentIdx;
		}

	}

	pop(){
		if(this.queue.length === 0){ return null };

		const data = this.queue[0];
		
		const lastData = this.queue.pop();
		
		if(this.queue.length > 0){
			this.queue[0] = lastData;
			this.shiftDown(0);
		}

		return data;
	}
	
    
  // 삭제 후 정렬
	shiftDown(index){
		
		const leftChildIdx = 2 * index + 1;
		const rightChildIdx = 2 * index + 2;

		let smallestIdx = index;

		if(
			leftChildIdx < this.queue.length &&
			this.queue[leftChildIdx].dist < this.queue[smallestIdx].dist)
		{
			smallestIdx = leftChildIdx;
		} 
		if(
			rightChildIdx < this.queue.length &&
			this.queue[rightChildIdx].dist < this.queue[smallestIdx].dist)
		{
			smallestIdx = rightChildIdx;
		}	
		
		if(smallestIdx !== index){
			const temp = this.queue[index];
			this.queue[index] = this.queue[smallestIdx];
			this.queue[smallestIdx] = temp;
            
              // 제귀 함수
			this.shiftDown(smallestIdx);
		}

	}

}