[Python] heapq 사용시 리스트를 heapify / 값 하나씩 heappush 차이점

프로그래머스 더 맵게 문제를 풀다가 리스트를 정렬하는 sort() 메소드를 사용하면 값은 나오는데 시간초과가 떠서,

배열을 heapq로 바꿔주는 heapify 대신 ( 제자리에서 힙으로 변환된다 )

원소 하나하나를 heappush 하면 힙의 불변성을 유지하며 push, pop 된다.

파이썬에 내장된 heapq는 이진 트리이며 최소힙을 사용한다고 한다.

공식문서의 heapq 설명

 

1. 리스트를 그대로 힙으로 변환할 때

import heapq

arr = [9, 3, 2, 1, 12, 10]
heapq.heapify(arr)
print(arr) //[1, 3, 2, 9, 12, 10]

heapify

2. 원소 하나하나 heappush 할 때

import heapq

arr2 = [9, 3, 2, 1, 12, 10]
new_arr = []
for i in arr2:
    heapq.heappush(new_arr, i)
print(new_arr) //[1, 2, 3, 9, 12, 10]