[자료구조] Priority Queue

Priority Queue

• FIFO(First In First Out) 형식
• 우선순위가 높은 데이터가 먼저 출력되는 형식

---

Heap

• 최대, 최소를 빠르게 찾기 위한 자료구조
• 배열에서는 $O(n)$이 걸린다면, 힙을 사용하면 $O(logn)$
• 완전이진트리
• 최대힙, 최소힙 두 종류

---

데이터 삽입, 삭제 원리

• (최소힙) 데이터 삽입 시, 가장 아래에 데이터 저장 후 부모 노드와 비교해가면서 작은 값이 부모 노드에 갈 수 있도록 위치 교환
• (최소힙) 데이터 삭제 시, 루트 노드를 삭제하고 가장 아래 데이터를 루트 노드로 옮기고, 왼쪽과 오른쪽의 크기와 비교해 더 작은 쪽과 위치 교환

import heapq

hq = []

heapq.heappush(hq, 1)
heapq.heappush(hq, 5)
heapq.heappush(hq, 3)

hq[0] # 1

heapq.heappop(hq) # 1
heapq.heappop(hq) # 3
heapq.heappop(hq) # 5

---

활용 1 - 중앙값 찾기

• 값이 순차적으로 들어올 때, 매번 정렬하여 중앙값을 찾으면 시간이 오래 걸린다.
• 최대힙, 최소힙을 활용하여 실시간으로 중앙값을 찾을 수 있다.

import heapq

arr = [1, 5, 2, 10, -99, 7, 5]
max_hq = []
min_hq = []

for num in arr:
		if len(max_hq) == len(min_hq):
		    heapq.heappush(max_hq, -num)
		else:
		    heapq.heappush(min_hq, num)
    
    if max_hq and min_hq and -max_hq[0] > min_hq[0]:
        max_value = heapq.heappop(max_hq)
        min_value = heapq.heappop(min_hq)
        heapq.heappush(min_hq, -max_value)
        heapq.heappush(max_hq, -min_value)
    print(-max_hq[0])