우선순위 큐(PriorityQueue) 이해하기

• 우선순위가 높은 값이 먼저 나오는 자료구조
• 일반적으로는 최소값 or 최대값 기준
• python에서는 heapq를 써서 min-heap(최소 힙)으로 구현

import heapq

heap = []
heapq.heappush(heap,4 )
heapq.heappush(heap,1 )
heapq.heappush(heap,7 )

print(heapq.heappop(heap)) # 1

-> heappush() : 값 추가
-> heappop() : 가장 작은 값 꺼내기

그 외의 케이스

• 튜플 (우선순위, 값) 형태로 넣기

heapq.heappush(heap, (priority, value))

• 최대 힙 구현하기
  -> heapq는 기본적으로 최소 힙이니까 음수로 변환해서 넣으면 된다!

heapq.heappush(heap, -x)
heapq.heappop(heap) * -1

• 기존 리스트를 힙으로 변환하는 함수heapify

heap = [4,1,7]
heapq.heapify(heap)

관련 코딩 테스트

[백준/Python] 11286)절댓값 힙
[백준/Python] 1927)최소 힙