파이썬 - heapq

< heapq >

• 힙 기능을 위해 제공하는 라이브러리
• 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현할 때 사용
• PriorityQueue 라이브러리를 사용할 수 있지만 코딩 테스트에서는 보통 heapq가 빠름

< 파이썬에서의 힙 >

• 최소 힙으로 구성되어 있어 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 O(NlogN)
• 보통 최소 힙 자료구조의 최상단 원소는 항상 가장 작은 원소이기 때문
• heapq.heappush(): 힙에 원소를 삽입할 때
• heapq.heappop(): 힙에서 원소를 꺼낼 때

# heapq로 최소힙 구현 예시

import heapq

def heapsort(iterable):
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for _ in range(len(h)):
    result.append(heapq.heappop(h))
  return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

• 파이썬은 최대힙을 제공하지 않기 떄문에 원소의 부호를 임시로 변경하는 방식 사용
• 힙에 원소를 삽입하기 전 잠시 부호를 반대로 바꾸었다가 원소를 꺼낸 뒤 다시 부호 바꿈

# 최대힙 예시

import heapq

def heapsort(iterable):
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable:
    heapq.heappush(h, -value)
  # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
  for _ in range(len(h)):
    result.append(-heapq.heappop(h))
  return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)