[파이썬] heapq 라이브러리

heapq는 우선순위 큐 기능을 구현하고자 할 때 사용된다. 

파이썬의 heapq 라이브러리는 최소 힙으로 구성되어 있다.

따라서 단순히 원소를 힙에 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)의 오름차순 정렬이 완료된다.

 

heapq의 메서드 

힙에 원소를 삽입할 때 -> heapq.heappush()

힙에서 원소를 꺼낼 때 -> heapq.heappop()

 

사용 예:

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, 6, 3, 5, 4, 7, 8, 9]

 

리스트를 힙으로 변환할 때 -> heapq.heapify()        ( 시간복잡도: O(N) )

사용 예:

result2 = [1,3,5,7,9,2,4,6,8,0]
heapq.heapify(result2)

print(result2) # [0, 1, 2, 6, 3, 5, 4, 7, 8, 9]