[자료구조/힙] 백준 11279 최대 힙 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11279번: 최대 힙

 

 

 

2. 문제 풀이

 최대 힙 자료구조를 구현하는 문제입니다.

 

2022.02.20 - [Algorithm] - [자료구조/힙] 백준 1927 최소 힙 - Python

[자료구조/힙] 백준 1927 최소 힙 - Python

 최소 힙과 매우 유사한 문제입니다. 최대 힙은 음수를 이용해서 구현합니다.

 음수의 최솟값에 -를 붙이면 최댓값이 됩니다. 이를 이용합니다.

 

 

 

3. 코드

import sys
import heapq
input = sys.stdin.readline

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

for _ in range(N):
    x = int(input())
    # x가 0이 아니면 push
    if x != 0:
        heapq.heappush(heap, -x)

    # x가 0이고 비어있지 않으면 pop
    elif heap:
        print(-heapq.heappop(heap))

    # x가 0이고 비어있으면 0 출력
    else:
        print(0)

 heapq 라이브러리는 최소 힙 자료구조를 지원합니다. 음수를 이용해서, 최솟값이 아니라 최댓값을 반환하도록 설계합니다.