[자료구조] 우선순위 큐

우선순위 큐(Priority Queue)는 일반적인 큐와 달리 데이터가 들어온 순서가 아닌 우선순위에 따라 처리되는 자료구조이다. 이는 특정 작업의 중요도에 따라 먼저 처리해야 하는 상황에서 매우 유용하게 사용된다.

우선순위 큐의 핵심은 우선순위를 기준으로 요소들을 정렬하여 관리하는 것이다. 예를 들어, 병원의 응급실에서는 환자가 도착한 순서대로 치료를 받는 것이 아니라, 상태가 위급한 환자가 먼저 치료를 받는다. 이러한 상황에서 우선순위 큐가 사용된다.

우선순위 큐의 구조

https://yoondii.tistory.com/2

우선순위 큐는 일반적으로 힙(Heap) 자료구조를 사용하여 구현된다. 힙은 완전 이진 트리의 일종으로, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉜다. 최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같다.

• 최대 힙(Max Heap): 루트 노드에 가장 큰 값이 위치하며, 이를 통해 최댓값을 빠르게 추출할 수 있다.
• 최소 힙(Min Heap): 루트 노드에 가장 작은 값이 위치하며, 이를 통해 최솟값을 빠르게 추출할 수 있다.

우선순위 큐의 연산

우선순위 큐에서 자주 사용되는 연산은 다음과 같다:

1. 삽입(Insertion): 새로운 요소를 우선순위 큐에 추가한다. 힙의 성질을 유지하기 위해 요소를 삽입한 후 상향 조정(Heapify Up) 과정을 통해 힙 속성을 복구한다.
2. 삭제(Deletion): 가장 높은(또는 낮은) 우선순위를 가진 요소를 제거한다. 보통 루트 노드를 제거하며, 제거한 후에는 힙의 마지막 요소를 루트로 옮긴 후 하향 조정(Heapify Down) 과정을 통해 힙 속성을 복구한다.
3. 조회(Peek): 가장 높은(또는 낮은) 우선순위를 가진 요소를 제거하지 않고 반환한다.

힙의 삽입 연산 과정

1. 새 요소 삽입: 새로운 요소를 힙의 마지막 위치에 삽입한다.
2. 상향 조정(Heapify Up): 삽입한 요소를 부모 노드와 비교하여 힙 속성을 유지한다. 최대 힙의 경우, 삽입한 요소가 부모 노드보다 크다면 두 노드를 교환한다. 최소 힙의 경우, 삽입한 요소가 부모 노드보다 작다면 두 노드를 교환한다.
3. 반복: 삽입한 요소가 부모 노드보다 크거나 작지 않을 때까지, 또는 루트에 도달할 때까지 상향 조정 과정을 반복한다.

예시: 최대 힙에 요소 15를 삽입

1. 힙의 현재 상태: [30, 20, 10, 5, 7, 9, 3]
2. 요소 15를 힙의 마지막에 삽입: [30, 20, 10, 5, 7, 9, 3, 15]
3. 상향 조정:
   • 15와 부모 노드 5를 비교하여 교환: [30, 20, 10, 15, 7, 9, 3, 5]
   • 15와 부모 노드 20을 비교(교환 필요 없음): [30, 20, 10, 15, 7, 9, 3, 5]

힙의 삭제 연산 과정

1. 최대/최소 요소 제거: 루트 노드(최대 힙의 경우 최대값, 최소 힙의 경우 최소값)를 제거한다.
2. 마지막 요소 이동: 힙의 마지막 요소를 루트 위치로 이동시킨다.
3. 하향 조정(Heapify Down): 루트에서 시작하여 자식 노드들과 비교하여 힙 속성을 유지한다. 최대 힙의 경우, 루트 요소가 더 큰 자식 노드와 교환한다. 최소 힙의 경우, 루트 요소가 더 작은 자식 노드와 교환한다.
4. 반복: 루트 요소가 자식 노드보다 크거나 작지 않을 때까지, 또는 리프 노드에 도달할 때까지 하향 조정 과정을 반복한다.

예시: 최대 힙에서 루트 요소 30을 삭제

1. 힙의 현재 상태: [30, 20, 10, 15, 7, 9, 3]
2. 루트 요소 30 제거: [3, 20, 10, 15, 7, 9]
3. 마지막 요소 3을 루트로 이동: [3, 20, 10, 15, 7, 9]
4. 하향 조정:
   • 3과 자식 노드 20, 10 중 더 큰 20과 교환: [20, 3, 10, 15, 7, 9]
   • 3과 자식 노드 15, 7 중 더 큰 15와 교환: [20, 15, 10, 3, 7, 9]
   • 3은 자식 노드들보다 크기 때문에 종료

파이썬에서의 우선순위 큐 사용 

from queue import PriorityQueue

q = PriorityQueue()
q_limit = PriorityQueue(maxsize=10) #사이즈 제한 가능

위와 같이 PriorityQueue 라이브러리를 활용하여 우선순위 큐를 만들 수 있다

 

삽입

q.put(3)
q.put(5, 'python') #우선순위, 값의 형태로 저장 가능

put 함수를 활용하여 저장할 수 있다.

반환

q.qet() # 우선순위가 가장 높은 값 반환

get 함수를 활용하면 큐의 값이 반환된다.

 

 

출처

https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)