heapq 모듈

• list에 heapq 모듈을 이용해서 원소를 push하거나, pop하면 기존 list 자료구조를 priority queue처럼 활용 할 수 있습니다.

import heapq
pq = []
heapq.heappush(pq, 3)

• 최소 힙(min heap) 만으로 동작합니다.
  : 오름차순

heapq의 함수

원소 추가, pop

• O(logN)

import heapq

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

print(pq) # [1, 3, 4, 7]이 아니다. pq자체는 정렬되지 않는다.

print(heapq.heappop(pq)) # 1
print(heapq.heappop(pq)) # 3
print(heapq.heappop(pq)) # 4
print(heapq.heappop(pq)) # 7

• 원소를 튜플(tuple) 형태로 넣으면 튜플의 빠른 인덱스부터 차례로 우선순위를 갖도록 정렬됩니다.

import heapq

pq = []
heapq.heappush(pq, (1, 4))
heapq.heappush(pq, (2, 1))
heapq.heappush(pq, (1, 7))
heapq.heappush(pq, (1, 3))

print(heapq.heappop(pq)) # (1, 3)
print(heapq.heappop(pq)) # (1, 4)
print(heapq.heappop(pq)) # (1, 7)
print(heapq.heappop(pq)) # (2, 1)

• 최대 힙으로 설정 (내림차순)

import heapq

nums = [4, 1, 7, 3, 8, 5]
pq = []

for num in nums:
  heapq.heappush(pq, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(pq)[1])  # index 1

• 클래스로 우선순위 재정의
  : 데이터 들어간 순서 반영

import heapq

class PriorityQueue():
  def __init__(self):
    self.pq = []
    self.count = 0
  def enqueue(self, priority, data):
    self.count += 1
    heapq.heappush(self.pq, (priority, self.count, data))
  def dequeue(self):
    heapq.heappop(self.pq)
  def display(self):
    print(self.pq)

pq = PriorityQueue()
pq.enqueue(2, 300)
pq.enqueue(1, 300)
pq.enqueue(1, 100)
pq.enqueue(1, 500)
pq.enqueue(3, 100)
pq.display()
# [(1, 2, 300), (1, 4, 500), (1, 3, 100), (2, 1, 300), (3, 5, 100)]

원소 삭제

• O(logN)
• list를 넘기면 가장 작은 원소 삭제 후 리턴
  (본체list도 삭제 반영)

heapq.heappop(heap)

기존 list에 heap(pq)반영

• O(N)

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap) # [1, 4, 7, 3, 8, 5]

heapify vs heappush

• 원소를 하나씩 heappush로 넣었을 때랑 배열 전체를 heapify로 heap으로 만들었을 때 차이가 있다.
• heapify는 최소값을 찾아서 부모와 위치 교환을 한다.
• heappush는 heap 정렬을 통해 오름차순 정렬을 한다.

import heapq

nums = [5, 4, 3, 2, 1]
heap = []

for num in nums:
    heapq.heappush(heap, num)
print(heap)  # [1, 2, 4, 5, 3]


nums = [5, 4, 3, 2, 1]
heapq.heapify(nums)
print(nums)  # [1, 2, 3, 5, 4]

• heappush 반복 vs heapify는 최솟값 pop 결과는 동일하지만, 내부 배열 모양과 구축 속도가 다릅니다.
• 성능상: 한 번에 만들 땐 heapify(O(n)), 순차 삽입은 heappush(O(n log n)).
• 힙 모양은 유일하지 않다 → 내부 상태가 달라도 둘 다 올바른 힙.

import heapq

seq = [7, 2, 9, 4, 1, 5, 6, 8, 3]

# 방식 A: heappush로 하나씩 넣기
pq_push = []
for x in seq:
    heapq.heappush(pq_push, x)
# -> 한 예: [1, 2, 5, 3, 4, 9, 6, 8, 7]

# 방식 B: 리스트 한 번에 heapify
pq_heapify = seq[:]          # 원본 복사
heapq.heapify(pq_heapify)
# -> 한 예: [1, 2, 5, 3, 7, 9, 6, 8, 4]

# 공통: 최솟값 pop
heapq.heappop(pq_push)     # 1
heapq.heappop(pq_heapify)  # 1

# pop 이후 내부 상태(한 예)
# pq_push   -> [2, 3, 5, 7, 4, 9, 6, 8]
# pq_heapify-> [2, 3, 5, 4, 7, 9, 6, 8]

referenced

• https://www.daleseo.com/python-heapq/
• https://daimhada.tistory.com/169
• https://ninefloor-design.tistory.com/216