우선순위 큐는 각 항목마다 연관된 우선순위가 있습니다. 우선순위 큐는 힙을 사용하여 구현합니다.
최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조입니다.
그래서, 리스트에서 가장 작거나 큰 요소에 반복적으로 접근하는 프로그램에 유용합니다.
시간복잡도 : O(log n)
리스트를 힙으로 변환하기
import heapq
list1 = [4, 6, 8, 1]
heapq.heapify(list1)
print(list1)
> [1, 4, 8, 6]
항목에 힙 삽입하기 > heapq.heappush(heap, item)
import heapq
h = []
heapq.heappush(h, (1, 'food'))
heapq.heappush(h, (2, 'fruit'))
heapq.heappush(h, (1, 'drink'))
print(h)
> [(1, 'drink'), (2, 'fruit'), (1, 'food')]
힙에서 가장 작은 항목 제거하고 결과 리턴
import heapq
list1 = [1,3,4,6]
heapq.heappop(list1)
print(list1)
> [3, 4, 6]
여러 리스트의 값을 이터레이터로 반환하기
for x in heapq.merge([1,4,7],[2,9,10]):
print(x)
> 1
> 2
> 4
> 7
> 9
> 10
우선순위가 가장 높은 자료를 가장 먼저 꺼낼 수 있는 자료 구조입니다.
import heapq
hq = []
heapq.heappush(hq, (30,'red'))
heapq.heappush(hq, (15,'blue'))
heapq.heappush(hq, (19,'white'))
print(hq)
> [(15, 'blue'), (30, 'red'), (19, 'white')]
first = heapq.heappop(hq)
print(first)
> (15, 'blue')
print(hq)
> [(19, 'white'), (30, 'red')]
second = heapq.heappop(hq)
print(second)
> (19, 'white')