[Python] sort vs heapq

코딩테스트 문제를 풀던 중, 다른 사람의 풀이에서 정렬을 할 때 sort를 사용하는 대신 heapq를 사용하는것을 보았다.

내가 알기론 heapq.heappush와 heapq.heappop은 둘 다 O(logn)의 시간이 걸린다.

그렇다면 heapq.heappush의 경우 처음부터 데이터를 하나씩 받아와 넣는다면, n개의 데이터를 heapq.heappush하므로 총 O(nlogn)이 걸려야 하는게 아닌가?

pop의 경우는 heappop이 훨씬 느리다.
heappop은 O(logN)이 걸리는 반면, 일반 pop 은 O(1)이 거리므로 heappop이 훨씬 느리다.

게다가 N번 수행하는거면 O(NlogN) vs O(N)으로 일반 pop이 훨씬 빠르다.

그렇다면 heapq는 언제 사용하면 좋을까?

코딩테스트 상황처럼 빈 리스트에 새 원소들을 추가하며 최종적으로 정렬된 리스트를 얻어야 하는 상황보다는 새로운 데이터가 추가되어도 항상 정렬 상태를 유지해야 하는 상황이거나, 이미 정렬되어있는 리스트에 새 원소를 추가하는 경우에 유용하게 쓰일 수 있을 것 같다.

즉,

heapq는 새로운 데이터가 추가되어도 항상 정렬된 상태를 유지하게 하거나, 이미 정렬되어 있는 상태를 이용하기 위해 사용하는것이지, 정렬을 빠르게 하는 것과는 일반 sort와 크게 차이가 없는 것 같다.....

데이터를 모두 입력받은 뒤 사용은 나중에 할 것이라면 heapq를 쓰느니 sort()를 쓰는게 더 낫다.