[Python] heapq (최소힙, 최대힙)

[Python] heapq (최소힙 & 우선순위 큐)

파이썬의 힙은 최소 힙으로 구성되어 있고 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다.

• heapq 내부 메서드

  • heapq.heappush(): 원소 삽입
  • heapq.heappop() : 원소 꺼내기

• heapq 예시

  # 힙 정렬을 heapq로 구현하는 예제
  import heapq
  
  def heapsort(iterable):
      h = []
      result = []
      # 모든 원소를 차례대로 힙에 삽입
      for value in iterable:
          heapq.heappush(h, value)
      # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
      for i 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)
  
  # 출력 결과
  [0,1,2,3,4,5,6,7,8,9]

• 최대 힙 예시

  # 파이썬은 최대 힙을 제공하지 않으므로 아래와 같이 부호를 변경하는 방식으로 최대 힙을 사용한다.
  import heapq
  
  def heapsort(iterable):
      h = []
      result = []
      # 모든 원소를 차례대로 힙에 삽입
      for value in iterable:
          heapq.heappush(h, -value)
      # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
      for i 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)
  
  # 출력 결과
  [9,8,7,6,5,4,3,2,1,0]