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]

referenced

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