우선순위 큐

💡 우선순위 큐

---

물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

• 일반적인 큐는 선입선출. 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것

• 우선순위 큐는 힙 이라는 자료구조를 이용하여 구현할 수 있다.

• 우선순위가 중간인 것이 삽입 되려고 할 때 삽입 과정에서는 뒤의 데이터까지 인덱스를 모두 한 칸씩 뒤로 밀어야 하는 번거로움이 발생. 힙은 삭제와 삽입 모두 부모와의 비교를 통해 이루어진다.

우선순위 큐를 힙 자료구조를 이용하여 구현할 수 있다.

💡 힙 자료구조

---

• 파이썬 heapq 모듈은 priority queue 제공

• 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들보다 작거나 같은 최소힙의 형태로 정렬
  
  
  
  

💡 힙 함수

---

• heapq.heappush(heap, item) : item을 heap에 추가

• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.

• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N))

• heapq.nlargest(n, iterable, key=None) :

nums = [1, 3, 6, 34, 5, 22, 67, -3, 56, -9]
print(heapq.nlargest(5, nums))
# nums에서 가장 큰 수 5개 출력

>>> [67, 56, 34, 22, 6]

💡 최대힙 만들기

---

y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

print(max_heap)

reference