파이썬 heapq

파이썬은 heapq 라는 자동으로 힙구조를 만들어주는 함수가 존재한다.
이 녀석을 활용하는 방법은 간단히 이 두가지만 알면 된다.

• heapq.push(리스트, 값) / 힙에 원소를 추가
• heapq.heappop(리스트) / 힙에서 루트 노드의 값을 pop.

import heapq

myli = []
heapq.heappush(myli, 1)
heapq.heappush(myli, 3)
heapq.heappush(myli, 5)
heapq.heappush(myli, 7)
heapq.heappush(myli, 2)
print(myli)
=> [1, 2, 5, 7, 3]

for i in range(len(myli):
	print(heapq.heappop(myli))
=> 
1
2
3
5
7

최소힙 그림판 에디션

저 heapq라는 녀석이 이 귀찮은 heapify를 대신해주는거다.
heap구조는 심지어 삭제 시간이 O(N)인 리스트보다 시간복잡도도 삽입, 삭제 둘다 O(logN)으로 훌륭하다!

import heapq

li = [1,3,5,7,9,2,4,6,8,0]

tmp = []
result = []
for i in li:
    heapq.heappush(tmp, i)
    
for i in range(len(li)):
    result.append(heapq.heappop(tmp))
print(result)

이제 heapq를 사용해서 아래와같이 정렬에도 써먹을 수가 있다. 고마워요 힙큐!