[Python]우선순위큐 백준 11286

   문제

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

전체적인 구현은 앞의 우선순위큐와 거의 동일하다.

절대값으로 변환하여 비교해주고 절대값이 같을때 작은경우가 부모노드가 될수있도록 

하면된다.절대값은 직접 구현할수도 있지만 너무 지저분해질거 같아서 abs()함수를 

사용하여 비교하였다.

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 abs(pq[a])<abs(pq[(a-1)//2]):  #절대값비교
                pq[a],pq[(a-1)//2]=pq[(a-1)//2],pq[a]
                a=(a-1)//2
            elif abs(pq[a])==abs(pq[(a-1)//2]):#절대값이 같을때는 작은거먼저
                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
            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 abs(pq[a*2+1])>=abs(pq[a*2+2]):#작은자식찾기
                    if abs(pq[a*2+1])==abs(pq[a*2+2]):
                        if pq[a*2+1]>pq[a*2+2]:#둘중작은거
                            child = a * 2 + 2
 
                    else:
                        child = a * 2 + 2
 
 
 
                if abs(pq[child])<abs(pq[a]):#자식이 더작다면 스왑
                    pq[child],pq[a]=pq[a],pq[child]
                    a=child
                    child=a*2+1
                elif abs(pq[child])==abs(pq[a]):#절대값이 같을때는 작은거
                    if pq[child]<pq[a]:
                        pq[child], pq[a] = pq[a], pq[child]
                        a = child
                        child = a * 2 + 1
                    else:
                        break
 
                else:#더이상 스왑할 필요없으면 멈춤
                    break