heapq 모듈 (heapq.heapify(), heapq.heappop(), heapq.heappush())

heap 모듈 프로그래머스의 야근지수 문제를 풀던 중 힙 정렬의 시간복잡도를 생각하게 됐습니다. heap 모듈을 우선 호출합니다. import heapq heapify() 아래는 works라는 리스트를 힙 구조로 바꿔주는 코드입니다. 이때 heapify()는 O(n)만큼의 시간복잡도가 요구됩니다. 파이썬의 힙구조는 기본적으로 최소 힙 형태입니다. works = [3,4,3] heapq.heapify(works) 주의 할 점은, works는 이미 리스트 형태인 객체를 heap배열로 바꾸는 것이기 때문에 O(n)의 시간복잡도가 소요됩니다. 위와 달리, 빈 리스트를 대상으로 힙 구조화를 할 시엔 아래와 같습니다. heapq.heappush() , heapq.heappop() works2 = [] heapq.h..

2020.10.30