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

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

---

알고리즘 분류

• 우선순위큐

문제풀이

이 문제는 최소힙과 아주 유사한 문제이다.
파이썬에서 제공하는 heapq모듈은 최소힙자료구조를 기반으로 한다.

따라서 최대힙을 위해서는 -를 붙여서 집어넣고 빼낼땐 절대값으로 빼내주었다.

힙은 2가지의 구조를 가진다.
Max Heap (최대힙) : 각 부모노드는 자식노드들 보다 항상 크거나 같다.
Min Heap (최소힙) : 각 부모노드는 자식노드들 보다 항상 작거나 같다.

소스코드

import heapq
import sys
input=sys.stdin.readline

n=int(input())
exp=[]
for _ in range(n):
  exp.append(int(input()))

heap=[]
heapq.heapify(heap)
for i in exp:
  if i==0 and len(heap)==0:
    print(0)
  elif i==0:
    print(abs(heapq.heappop(heap)))
  else:
    heapq.heappush(heap,-i)