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

출처 - https://hannom.tistory.com/36

 

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오나 우선순위 큐는 다르다.

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

우선순위가 다른 데이터 뿐만 아니라 같은 데이터가 존재할 수도 있다.

 

우선순위 큐를 구현하는 방법은 세 가지로 나뉘어진다.

- 배열을 기반으로 구현하는 방법

- 연결리스트를 기반으로 구현하는 방법

- 힙(Heap)을 이용하는 방법

 

우선순위 큐는 주로 힙(Heap)을 이용해서 구현하는 것이 성능상으로 가장 좋다.

 

힙을 기반으로 우선 순위 큐를 구현하고자 한다.

힙의 구현을 위해 데이터의 저장과 삭제 방법을 알아보자

 

1) 데이터 저장 로직

 

위 힙 구조 안에 있는 숫자를 데이터 겸 우선순위라고 하고 숫자가 작을수록 우선순위가 높다고 가정하자

 

위 상황에서 2를 저장한다고 가정 시,

새로운 데이터는 우선순위가 제일 낮다는 가정하에 마지막 위치에 저장한다.

그리고 부모 노드와 우선순위를 비교하여 위치가 바뀌어야 한다면 바꿔주고 제 자리를 찾을때까지 반복한다.

 

위에서 언급한 '마지막 위치'는 노드를 추가한 이후에도 완전 이진 트리가 유지되는 마지막 레벨의 가장 오른쪽 위치를 의미한다.

 

 

2를 마지막 위치에 추가한 뒤에 부모 노드인 7과 비교를 한다.

 

2와 7의 위치를 서로 바꾼 후 부모 노드 3과 비교를 한다.

 

3과 2의 위치를 바꾼 뒤 1과 비교를 한다.

1과 비교를 하였을 때 2는 1보다 우선순위가 낮으므로 2는 제자리를 찾았다.

 

위의 구조가 결과가 되는 것인데 힙의 조건을 만족하고 있다.

 

 

2) 데이터 삭제 로직

우선순위 큐의 삭제는 가장 높은 우선 순위의 데이터 삭제를 의미한다.

힙에서 루트 노드를 삭제한다는 것은 그다지 어렵지 않다.

하지만 루트 노드를 삭제한 뒤에 빈 루트노드는 어떻게 채울까?

 

 

마지막 노드를 루트 노드의 자리로 옮긴 뒤 자식 노드와의 비교를 통해 제자리를 찾아가게 하는게 포인트

 

마지막 노드를 루트 노드로 옮긴 뒤 자식 노드와 비교를 한다.

이 때 두 개의 자식 노드중 우선 순위가 높은 노드와 교환을 한다

 

자식 노드 2와 6중에서 우선순위가 높은 2와 교환한다.

 

 

자식 노드 20과 비교했을 때 우선순위가 7이 더 높으므로 현재 제자리를 잘 찾았다.