heapq

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

프로그래머스 더 맵게 문제를 풀다가 리스트를 정렬하는 sort() 메소드를 사용하면 값은 나오는데 시간초과가 떠서, 배열을 heapq로 바꿔주는 heapify 대신 ( 제자리에서 힙으로 변환된다 ) 원소 하나하나를 heappush 하면 힙의 불변성을 유지하며 push, pop 된다. 파이썬에 내장된 heapq는 이진 트리이며 최소힙을 사용한다고 한다. 1. 리스트를 그대로 힙으로 변환할 때 import heapq arr = [9, 3, 2, 1, 12, 10] heapq.heapify(arr) print(arr) //[1, 3, 2, 9, 12, 10] 2. 원소 하나하나 heappush 할 때 import heapq arr2 = [9, 3, 2, 1, 12, 10] new_arr = [] for i i..