[Baekjoon]백준 11279 최대 힙(실버 2) - Python

문제설명

예제

문제를 살펴보면 최대 힙을 이용하여 자연수를 넣고, 0을 입력하게 되면 가장 큰 값을 출력함과 동시에

해당 값을 배열에서 제거하면 된다 파이썬에는 heapq라는 모듈이 존재하지만 이는 최소 힙이 구현되어 있기

때문에 자연수를 넣을 때, -1, -2와 같은 방식으로 넣게 되면 최대힙으로 구현할 수 있다

 

최대 힙에 대해 간단하게 설명하기 위해 최대 트리에 대해 설명이 필요하다

최대 트리란 각 노드의 key값이 그 자식의 key값보다 크거나 같은 트리이다

최대 힙은 이런 최대 트리의 특징을 가지면서 동시에 완전 이진 트리라는 점이 특징이다

완전 이진 트리는 노드를 삽입할 때 왼쪽부터 차례대로 삽입한다는 점이 있다

         1

     2     3

4 

와 같은 형식이라고 생각하면 되며, 만약 다음과 같은 형식이라면 이는 완전 이진 트리가 아니게 된다

         1

     2     3

        4

이러한 특징을 알고 있다면 해당 코드를 작성하는 것에 있어 큰 어려움이 없을것이라 생각한다

import sys
import heapq
input = sys.stdin.readline

cnt = int(input())
heap = []
for _ in range(cnt):
    x = int(input())
    if x == 0:
        if heap:
            print(-heapq.heappop(heap))
        else:
            print(0)
    else:
        heapq.heappush(heap, -x)