🫧 우선순위 큐
우선순위 큐는 우선순위가 갖아 높은 데이터를 갖아 먼저 삭제하는 자료구조이다.
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
| 자료구조 | 추출되는 데이터 |
|---|---|
| 스택(Stack) | 가장 나중에 삽입된 데이터 |
| 큐(Queue) | 가장 먼저 삽입된 데이터 |
| 우선순위 큐(Priority Queue) | 가장 우선순위가 높은 데이터 |
🫧 우선순위 큐 구현 방법
- 리스트를 이용하여 구현
- 힙(Heap)을 이용하여 구현
데이터 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 다음과 같다.
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다.(힙 정렬)
이 경우 시간 복잡도는 O(logN)이다.
힙(Heap)
힙은 완전 이진 트리 자료구조의 일종이다.
완전 이진 트리란 루트(root) 노트부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미한다.
- 최소 힙 : 부보 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
- 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
❗️ 이 때 키 값의 대소 관계는 부모-자식 간에만 성립하고, 형제 노드 사이에는 대소 관계가 정해지지 않는다.
1️⃣ heap 생성 - heapify
[]로 초기화 된 리스트를 사용하거나, 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환할 수 있다.
최소 힙의 형태로 정렬된다.
import heapq
heap1 = []
heap2 = [50 ,10, 20]
heapq.heapify(heap2)2️⃣ heap 원소 추가 - heappush
O(logN) 시간 복잡도를 가진다.
import heapq
heap1 = []
heapq.heappush(heap1, 50)
heapq.heappush(heap1, 10)
heapq.heappush(heap1, 20)
print(heap1) # [10, 50, 20]
heap2 = [50 ,10, 20]
heapq.heapify(heap2)
print(heap2) # [10, 50, 20]3️⃣ heap 원소 삭제 - heappop
O(logN) 시간 복잡도를 가진다.
힙에서는 항상 루트 노드를 제거한다.
result = heapq.heappop(heap)
print(result) # 10
print(heap1) # [20, 50]원소를 삭제하지 않고 가져오고 싶으면 [0] 인덱싱을 통해 접근한다.
result2 = heap[0]
print(result2) # 20
print(heap1) # [20, 50]🫧 구현 예제
Python에서는 기본적으로 최소 힙으로 구현된다.
import sys
import heapq
input = sys.stdin.readline
def heapsort(iterable):
h = []
result = []
# 모든 원소를 차례때로 힙에 삽입
for value in iterable:
heapq.heappush(h, value)
# 힙에 삽입된 모든 원소를 차례때로 꺼내어 담기
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
n = int(input())
arr = []
for i in range(n):
arr.append(int(intpu()))
res = heapsort(arr)
for i in range(n):
print(res[i])🌟 최대 힙 구현하기
Python의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서 (-item, item)의 튜플 형태로 원소를 추가해주면, 튜플의 첫 번째 원소를 우선순위로 힙을 구성하기 때문에 최대 힙을 구현할 수 있게 된다.
import heapq
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))
print(max_heap) # [(-9, 9), (-7, 7), (-3, 3), (-1, 1), (-5, 5)]heappop을 사용하게 되면 힙에 있는 최댓값이 반환된다. 이때 실제 원소 값은 튜플의 두 번째 자리에 저장되어 있으므로 [1] 인덱싱을 통해 접근한다.
max_item = heapq.heappop(max_heap)[1]
print(max_item) # 9