1927 최소힙

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

 

힙2

힙1과 같음

 

구현:

import sys
input = sys.stdin.readline
heap=[0]

def add(x):
    heap.append(x)
    l=len(heap)-1

    while l>1:
        if heap[l]<heap[l>>1]:
            heap[l>>1],heap[l]=heap[l],heap[l>>1]
            l>>=1
        else:
            return

def rm():
    if len(heap)<=1: return 0
    heap[1],heap[-1]=heap[-1],heap[1]
    res=heap.pop()
    heapify()
    return res

def heapify(node=1):
    l=len(heap)
    left,right=0,0
    tmp=node*2
    if tmp<l:
        left=tmp
        if left+1 < l:
            right=left+1
    else : return
    if right:
        tmp=[left,right][heap[left]>heap[right]]
    else:
        tmp=left
    if heap[tmp]<heap[node]:
        heap[node],heap[tmp]=heap[tmp],heap[node]
    heapify(tmp)

for _ in range(int(input())):
    x=int(input())
    if x==0:
        
        print(rm())
    else:
        add(x)

 

모듈:

import sys
import heapq
input = sys.stdin.readline

h=[]
for _ in range(int(input())):
    x=int(input())
    if x==0:
        try: print(heapq.heappop(h))
        except:print(0)
    else:
        heapq.heappush(h,x)