[백준] 11279 최대힙 파이썬 풀이 (힙)

힙이란?

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리

 

 

최대힙과 최소힙

최소힙은 최소값이 가장 상위에 있고

부모 노드가 자식 노드보다 값이 작아야한다.

 

최대 힙은 최대값이 가장 상위에 있고

자식 노드가 부모 노드보다 값이 작아야한다.

 

문제

값을 넣고 0을 입력하면 배열에서 가장 큰 값을 출력해라

 

문제풀이

• heapq에서는 최소 힙을 제공하기때문에 값을 -를 붙인 key값으로 heap에 넣는다.
• 그러면 가장 큰 값이 가장 상위에 올라가게된다.
• 그리고 출력할때는 value값으로 출력한다.

 

 

 

코드

import sys
import heapq as hq

numbers = int(input())
heap = []

for i in range(numbers):
    num = int(sys.stdin.readline())
    # print(num)
    if num >0:
        hq.heappush(heap,(-num,num)) #-를 하여 제일 큰 값이 맨 앞에 가도록 한다
    else:
        if heap:
           print(hq.heappop(heap)[1]) #맨앞에 수를 꺼내는데 value값을 꺼낸다 (-5,5)
        else:
            print(0)