[Python]우선순위큐 백준 11279

   문제

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

앞서 힙정렬을 구현할때 사용하였으므로 따로 설명을 붙이지는 않겠다.

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