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.heappush(4)

>>> [4]

heapq.heappush(9)

>>> [4, 9]

heapq.heappush(3)

>>> [3, 9, 4]

works2 리스트는 heappush() 메소드로 인해 힙구조를 가지게 됐지만,

heapify()와는 달리 heappush()의 시간 복잡도는 O(log(n))이 됩니다.

이는 heappush()의 반대인 heappop()도 마찬가지로 동일한 시간 복잡도를 가집니다.

works = [3, 9, 4]
heapq.heappop(works)

>>> [4, 9]

결론

heapq.heapify()의 시간복잡도는 O(n)
heapq.heappush() , heapq.heappop()의 시간복잡도는 O(log(n))