[파이썬] 백준 11279 : 최대 힙

[파이썬] 백준 11279 : 최대 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

실버 2

우선순위 큐, 자료구조

---

최소 힙을 응용해서 푸는 문제.

파이썬의 heapq모듈은 최소 힙을 구현할 수 있도록 만들어져 있기 때문에 최대 힙을 구하려면 약간의 조작이 필요했다.

 

코드

import heapq, sys; input = sys.stdin.readline
N = int(input())
heap = []
for i in range(N):
    h = int(input())
    if h != 0:
        heapq.heappush(heap, (-h, h))
    else:
        try:
            print(heapq.heappop(heap)[1])
        except:
            print(0)

 

heappush로 입력받은 값의 음수와 양수를 튜플 형태로 넣어주고,

heappop으로 튜플의 0번째 인덱스를 기준으로 최솟값을 가진 것을 선택해 1번째 인덱스에 있는 양수 값을 반환한다.

(-4, 4)가 heappop으로 반환된다면, 1번째 인덱스의 4값이 곧 최댓값이 된다.