들어가기 전에
일반적인 큐(queue)는 먼저 들어간 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장되는 선형 자료구조이다.
그러나, 오늘 정리할 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다
배열, 연결 리스트, 힙 을 활용해 우선순위 큐를 구현할 수 있는데 원소의 추가, 제거에 있어 힙이 O(logN)의 시간 복잡도를 보장하기 때문에 힙을 사용해 우선순위 큐를 구현한다.
먼저 힙이 어떤 특징을 가지는지부터 알아보자
힙
정의
- 힙은 완전 이진 트리의 일종으로, 우선순위 큐를 위해 만들어진 자료 구조이다.
- 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료구조이다.
❓ 완전 이진 트리?
💡 이진 트리는 각 노드가 두 개의 자식을 갖는 트리를 말한다. 즉, 각 노드는 자식이 없거나 한 개 또는 두 개를 갖는 것이다.
완전 이진 트리는 마지막 레벨은 꽉 차 있지 않아도 되며, 노드가 왼쪽에서 오른쪽으로 채워진 트리를 말한다.
특징
- 부모 노드와 자식 노드 간에 대소 관계가 성립한다.
- 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙
- 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙
- 가장 높은 우선순위를 가지는 노드가 항상 root 노드에 위치하게 되며, 이 특징을 이용해
우선 순위 큐와 같은 자료형을 구현할 수 있다. - 원소의 추가, 제거 시간복잡도는
O(logn)이다.
❓
O(logN)인 이유?
💡 힙은 완전 이진 트리이므로 높이가logN이다.
원소 추가와 제거 연산은 힙 내에서 노드를 올바른 위치로 이동시키는 과정을 포함한다. 이 과정에서는 부모 노드와 자식 노드 사이의 비교 및 교체 작업이 이루어진다.
이 과정은 힙의 높이에 비례한다. 따라서 시간복잡도는O(logN)이다.
정의
- 데이터를 검색하고 추출할 때 우선순위에 따라 처리한다.
- 우선순위가 높은 요소가 큐의 앞쪽에 위차한다.
- 요소를 삭제할 때 가장 높은 우선수위를 가진 요소가 삭제된다.
- 우선순위가 가장 높은 원소의 확인은
O(1)이 소요된다. - 원소의 추가 및 제거에는
O(logN)이 소요된다.
활용
파이썬에서 힙을 활용해 우선순위 큐를 구현할 수 있다.
기본적으로 최소 힙의 구조를 갖는다.
import heapq
# 우선순위 큐 생성
pq = []
# 요소 추가
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
heapq.heappush(pq, 2)
# 우선순위에 따라 요소 추출
while pq:
print(heapq.heappop(pq))
# 출력 결과:
# 1
# 2
# 3
# 4최대 힙 구현하기
import heapq
# 빈 최대 힙 생성
max_heap = []
# 요소 추가 (음수로 변환하여 최대 힙으로 사용)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -2)
# 최대 힙에서 요소 추출 (음수로 변환된 값을 다시 양수로 변환)
while max_heap:
print(-heapq.heappop(max_heap))
# 출력 결과:
# 4
# 3
# 2
# 1힙을 활용하지 않는다면 배열을 활용해 직접 구현할 수 있다.
1) 루트 노드는 배열의 1번 인덱스에 위치한다.
2) 부모 노드의 인덱스가 i라고 하면 왼쪽 자식 노드의 인덱스는 2 i, 오른쪽 자식 노드의 인덱스는 2 i + 1이다.
3) 원소를 삽입하는 경우, 배열의 맨 끝에 삽입한 뒤 해당 노드의 부모 노드와 비교해가며 힙의 성질을 만족시킨다.
4) 원소를 제거하는 경우, 배열의 맨 끝 노드와 루트 노드를 교체한 뒤 맨 끝 노드를 삭제하고, 교체된 루트 노드에 대해 자식 노드와 비교해가며 힙의 성질을 만족시킨다.
위 과정을 코드로 구현하면 아래와 같다.
import sys
input = sys.stdin.readline
heap = [0]
for _ in range(int(input())):
x = int(input())
if x == 0: # 원소 삭제
if len(heap) == 1:
print(0)
else:
print(heap[1])
# 마지막 인덱스 원소와 바꾸고 마지막 원소를 삭제
temp = heap[1]
heap[1] = heap[len(heap) - 1]
heap.pop() # 마지막 원소 삭제
idx = 1
# 범위를 벗어나지 않는 경우 자식 노드와 비교하며 최소 힙 만족할 때까지 스왑
while idx * 2 < len(heap):
left_child = idx * 2
right_child = idx * 2 + 1
min_child = left_child
if right_child < len(heap) and heap[right_child] < heap[left_child]:
min_child = right_child
if heap[idx] <= heap[min_child]:
break
temp = heap[idx]
heap[idx] = heap[min_child]
heap[min_child] = temp
idx = min_child
else: # 자연수 들어온 경우 즉, 원소 삽입
heap.append(x)
idx = len(heap) - 1
if idx > 1:
# 부모 노드와 자식 노드를 비교해가며 최소 힙 만족할 때까지 스왑
while heap[idx // 2] > heap[idx]:
temp = heap[idx]
heap[idx] = heap[idx // 2]
heap[idx // 2] = temp
idx = idx // 2PriorityQueue vs heapq
파이썬은 PriorityQueue 를 아예 제공하고 있다.
from queue import PriorityQueue그렇다면 왜 우선순위 큐를 구현하는 데 PriorityQueue를 사용하지 않고 굳이 heapq를 사용하는 것일까?
그 이유는, PriorityQueue는 멀티스레딩 환경에서 안전하게 사용할 수 있는 우선순위 큐를 구현하는 반면, heapq는 단일 스레드 환경에서 사용되기 때문이다.
스레드 간 동기화가 필요하거나 멀티스레딩 환경의 경우 PriorityQueue를 사용하는 것이 좋겠지만, 코딩 테스트를 준비하는 경우 그렇지 않기에 heapq를 사용해 우선순위 큐를 구현한다.
정리
- 힙은 최대 힙, 최소 힙으로 나뉜다.
- 힙을 사용해 우선 순위 큐를 구현할 수 있다.
- 파이썬에서
heapq를 사용해 우선 순위 큐를 구현할 수 있다. - 우선순위 큐에서 원소의 추가, 제거 작업의 시간복잡도는
O(logN)이다. - 우선 순위 큐는 자료 구조가 아니라 추상적인 데이터 타입이다.
참고 자료
