최대 힙

11279번: 최대 힙

 

나의 풀이

import heapq
import sys
input = sys.stdin.readline

n_ct = int(input())
hq = []

for _ in range(n_ct):
    now_n = int(input())
    
    if now_n:
        heapq.heappush(hq, -now_n)
    else:
        if not hq:
            print(0)
        else:
            print(-heapq.heappop(hq))

 

시간 복잡도

for _  in range(n_ct) : n개의 수 순회 ( 선형 시간 복잡도 )
    heapq 연산 ( 로그 시간 복잡도 )
해당 알고리즘은 선형 로그 시간 복잡도 : O(nlogn)