✅ 우선순위 큐와 힙

우선순위 큐는 각 항목마다 연관된 우선순위가 있습니다. 우선순위 큐는 힙을 사용하여 구현합니다.

힙

최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조입니다.
그래서, 리스트에서 가장 작거나 큰 요소에 반복적으로 접근하는 프로그램에 유용합니다.
시간복잡도 : O(log n)

• 힙을 사용하는 이유
  - 배열에 데이터를 넣고 최대/최소값을 찾으면 시간 복잡도는 O(n)
  • 힙에 데이터를 넣고 최대/최소값을 구하면 O(log n) 이 걸림

1-1. heapq 모듈

리스트를 힙으로 변환하기

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')