[Python]우선순위큐 백준 1927

 문제

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

잘려고 하다가 최대힙에서 부호만 바꾸어주면 되는거 같아서 이렇게 작성하고 잔다.

스왑하는 부분만 부호를 바꾸어주면된다.

import sys
input=sys.stdin.readline
pq=[]
pqlen=0#길이
 
N=int(input())
while N>0:
    N-=1
    x=int(input())
    if x>0:#push
        pq.append(x) #제일끝에 추가해준다
        pqlen += 1
        a=pqlen-1
        while a>0:#힙구조 만들기
            if pq[a]<pq[(a-1)//2]:  #부모보다 크다면 바꾸어준다 끝까지 도달하거나 바꿀필요가 없을때까지
                pq[a],pq[(a-1)//2]=pq[(a-1)//2],pq[a]
                a=(a-1)//2
            else:
                break
 
 
    elif x==0:#pop
        if pqlen==0:
            print(0)
        else:
            print(pq[0])
            pq[0]=pq[pqlen-1]
            pq.pop()
            pqlen-=1
            a=0 #루트노드부터 출발
            child=1
            while child<=pqlen-1:#힙구조 만들기 길이를 초과하지 않을때까지
                if a*2+2<=pqlen-1 and pq[a*2+1]>pq[a*2+2]:#작은자식찾기
                    child=a*2+2
 
                if pq[child]<pq[a]:#자식이 더작다면 스왑
                    pq[child],pq[a]=pq[a],pq[child]
                    a=child
                    child=a*2+1
                else:#더이상 스왑할 필요없으면 멈춤
                    break