Priority Queue (우선순위 큐)
개요
우선순위 큐(Priority Queue)란 우선순위 큐(Priority Queue)란 큐(Queue) 자료구조의 일종으로, 각 요소에 우선순위가 부여되어 우선순위가 높은 요소가 먼저 처리되는 구조를 말한다.
일반 Queue와의 차이점
왜 우선순위가 앞에 붙을 것인가? 답은 간단하다.
일반 큐와 우선순위 큐의 가장 큰 차이점은 데이터 처리 순서이다. 일반 큐에서는 가장 먼저 삽입된 데이터가 가장 먼저 처리되지만, 우선순위 큐에서는 우선순위가 높은 데이터가 먼저 처리된다.
•
일반 큐: 선입선출 (FIFO)
•
우선순위 큐: 우선순위에 따라 처리 순서 결정
왜 우선순위가 앞에 붙는가? 그 답은 간단하다. 우선순위 큐는 대기 중인 작업 중에서 더 중요한 작업을 먼저 처리하기 위해 설계되었다. 예를 들어, 병원의 응급실에서 환자를 진료할 때, 더 위급한 환자를 먼저 진료하는 것이 더 중요하다. 이처럼 우선순위 큐는 긴급한 작업을 우선 처리해야 하는 상황에서 매우 효과적이다.
Heap (힙)
힙이란 완전 이진 트리의 일종으로, 특정한 우선순위 규칙을 따르는 자료구조이다. 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap) 두 가지 종류가 있으며, 각각의 힙은 특정한 정렬 조건을 만족해야한다.
힙으로서 만족해야하는 조건들은 다음과 같다:
1.
완전 이진 트리 구조
•
힙은 완전 이진 트리(Complete Binary Tree)여야 한다. 이는 트리의 모든 레벨이 꽉 차 있어야 하며, 마지막 레벨에만 일부 비어 있을 수 있지만, 그 비어 있는 자리는 반드시 오른쪽에서 왼쪽으로 채워져야 한다.
2.
힙 속성
•
최대 힙: 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같아야 한다. 즉, 가장 큰 값이 루트 노드에 위치하게 된다.
•
최소 힙: 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같아야 한다. 즉, 가장 작은 값이 루트 노드에 위치하게 된다.
우선순위 큐는 힙(Heap) 자료구조를 이용하여 구현하는 것이 일반적이며 보통 최소 힙을 사용하여 구현된다. 최소 힙은 우선순위가 낮은(작은) 요소를 먼저 처리할 수 있는 구조이기 때문이다. 힙을 사용하여 우선순위 큐를 구현하면 삽입과 삭제 연산이 모두 의 시간 복잡도로 효율적으로 처리된다.
Heap 이 만들어지는 과정 설명
힙(Heap)이 만들어지는 과정을 예시를 통해 알아보자. 여기서는 최소 힙을 사용하기로 한다.
예시: 숫자 [5, 3, 8, 4, 1, 7]을 최소 힙으로 만드는 과정
위 과정을 다시 정리해보자면,
•
새로운 요소가 삽입될 때는 트리의 가장 마지막 위치에 추가된다.
•
그 후, 부모 노드와 비교하여 힙 속성을 만족할 때까지 부모와 교환하며 위로 올라간다. 이 과정을 힙업(Heapify Up) 또는 상향식 정렬이라고 한다.
•
최소 힙에서는 부모 노드가 자식 노드보다 항상 작아야 하므로, 교환을 반복하여 힙 속성을 유지한다.
우선순위 큐의 구현 (by Heap, Python)
여러가지 방법이 존재하나, 가장 쉽고 빠르게 구현될 수 있는 Heap으로 하는 구현 방식을 설명해보고자 한다.
import heapq
# 빈 우선순위 큐 생성
priority_queue = []
# 요소 삽입 (우선순위, 값)
heapq.heappush(priority_queue, (1, '작업 1')) # 우선순위 1
heapq.heappush(priority_queue, (3, '작업 3')) # 우선순위 3
heapq.heappush(priority_queue, (2, '작업 2')) # 우선순위 2
# 우선순위가 가장 높은 요소(가장 작은 우선순위 값) 추출
highest_priority = heapq.heappop(priority_queue)
print(highest_priority) # (1, '작업 1')
C++
복사
•
정말 간단하다. 사실 우선순위 큐가 그냥 힙 그 자체다.
최단경로 문제에서의 우선순위 큐의 활용에 관하여
우선순위 큐는 최단 경로 알고리즘에서 중요한 역할을 한다. 대표적인 예로 다익스트라 알고리즘을 들 수 있다. 다익스트라 알고리즘에서는 각 노드의 최단 거리를 우선순위 큐를 통해 관리하며, 현재까지의 최단 거리가 작은 노드를 우선적으로 선택한다.
다익스트라 알고리즘에서의 기본적인 흐름은 다음과 같다:
1.
출발 노드에서 다른 모든 노드까지의 거리를 무한대(∞)로 설정하고, 출발 노드는 0으로 설정한다.
2.
현재까지의 최단 거리가 가장 작은 노드를 우선순위 큐에서 꺼내 그 노드의 인접한 노드들을 확인한다.
3.
인접 노드를 통해 가는 경로가 더 짧으면, 그 노드의 거리를 갱신하고 우선순위 큐에 다시 넣는다.
4.
모든 노드를 처리할 때까지 이 과정을 반복한다.
이 과정에서 우선순위 큐는 가장 작은 비용으로 이동할 수 있는 노드를 빠르게 선택할 수 있도록 도와준다.
요약
•
우선순위 큐(Priority Queue)란 우선순위 큐(Priority Queue)란 큐(Queue) 자료구조의 일종으로, 각 요소에 우선순위가 부여되어 우선순위가 높은 요소가 먼저 처리되는 구조를 말한다.
•
힙(Heap)은 완전 이진 트리를 기반으로 한 자료구조로, 우선순위 기준에 따라서 정렬하는 트리이다.
•
우선순위 큐는 힙(Heap)으로 간단하게 구현 가능하다.
REFERENCES
Written by Changyu Lee