[Python] heapq 모듈 사용하기

👩heapq 모듈

파이썬에서 heap을 구현하기 위해서는 heapq(힙큐) 내장 모듈을 사용한다.

  import heapq

🙋‍♀️ 최소 힙 사용하기

heap = []

• heapq 모듈을 사용한다면 일반 리스트를 최소힙처럼 사용할 수 있게 된다.
• heapq 모듈의 삽입, 삭제 함수를 호출할 때마다 생성한 리스트를 인자로 넘겨주어야 한다.

☝️원소 추가: heapq.heappush()

• heapq.heappush(대상 리스트, 추가할 원소)
  • 시간복잡도: O(logN)

  heapq.heappush(heap, 1)
  heapq.heappush(heap, 10)
  heapq.heappush(heap, 2)
  
  print(heap) # [1, 2, 10]
  

• 최소힙이기 때문에 가장 작은 값은 인덱스 0에 위치하게 된다.
  • heap[0]를 출력할 경우 최소값을 얻을 수 있다.

❕여기서 주의❕

• 그렇다고 인덱스 1에 두 번째로 작은 값이 들어있는 것은 아니다!

✌️원소 삭제: heapq.heappop()

• heapq.heappop(대상 리스트)
  • 시간복잡도: O(logN)

• 최소 값이 반환되게 된다.

  print(heapq.heappop(heap)) # 1
  print(heapq.heappop(heap)) # 2
  print(heap) # [10]
  

• 인덱스를 통해서 값을 삭제하지 않고 얻을 수 있다.

  print(heap[0]) #10
  

👌리스트를 힙으로! : heapq.heapify()

• heapq.heapify(대상 리스트)
  • 시간복잡도: O(N)

  lst = [1, 10, 2, 5]
  heapq.heapify(heap)
  print(lst) # [1, 2, 5, 10]
  

🙋‍♀️ 최대힙

• (우선 순위, 값) 형태의 튜플을 heap에 추가함으로써 최대힙을 구현할 수 있다.

  lst = [2, 5, 4, 9, 1]
  heap = []
  
  for i in lst:
    heapq.heappush(heap, (-i, i)) # 가장 큰 값이 가장 높은 우선순위를 가지게 된다.
  
  print(heap) # [(-9, 9), (-5, 5), (-4, 4), (-2, 2), (-1, 1)]
  
  while heap:
    print(heapq.heappop(heap)[1]) # 9 5 4 2 1
  
  

📃 참고

• https://www.daleseo.com/python-heapq/
• https://docs.python.org/ko/3/library/heapq.html