[Python] 우선순위 큐(Priority Queue), 힙(Heap)

1. 우선순위 큐(Priority Queue)

우선순위가 가장 높은 순서대로 추출된다.

* 큐(Queue) : 선입선출(FIFO), 가장 먼저 삽입된 데이터가 가장 먼저 추출된다. 

 

2. 힙(Heap)

데이터에서 최대값과 최소값을 가장 빠르게 찾을 수 있도록 만들어진 이진 트리

최대값을 구하기 위한 구조(최대힙, Max Heap), 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류 가능

 

3. 우선순위 큐 / 힙

우선순위 큐를 구현할 때는 시간 복잡도 측면에서 힙을 이용하는 것이 훨씬 효율적이다.

 

4. 파이썬에서 제공하는 라이브러리

우선순위큐 라이브러리

from queue import PriorityQueue

pq = PriorityQueue() # 우선순위 큐 생성
pq = PriorityQueue(maxsize=10) # 최대 크기를 10인 우선순위큐

pq.put((1,'a'))
pq.put((0,'b')) # 원소 추가

print(pq.get()) # 출력 : (0, 'b') -> 추출되며 큐에서 삭제됨
print(pq.qsize()) # 출력 : 1

 

힙큐 라이브러리

import heapq

arr = []
heapq.heappush(arr,3) # 힙 원소 추가
heapq.heappush(arr,1)
heapq.heappush(arr,2)

print(arr) # 출력 : [1, 3, 2]

heapq.heappop(arr)

print(arr) # 출력 : [2, 3]

arr2 = [10,2,7,11]
heapq.heapify(arr2) # 배열을 힙으로 변경

print(arr2) # 출력 : [2, 10, 7, 11]