[BOJ]11286 절대값 힙

11286 절대값 힙

import heapq
import sys
n = int(sys.stdin.readline())
q = []
for i in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        if len(q) == 0:
            print(0)
        else:
            small = heapq.heappop(q)
            temp = [small]
            while len(q)!=0 and small[0]==q[0][0]:
                temp.append(heapq.heappop(q))
            mins= min([t[1] for t in temp])
            print(mins)
            temp.remove((abs(mins),mins))
            for t in temp:
                heapq.heappush(q,t)

    else:
        heapq.heappush(q, (abs(x),x))

import sys
import heapq

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

for _ in range(numbers):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, (abs(num), num))
    else:
        try:
            print(heapq.heappop(heap)[1])
        except:
            print(0)

➡️ .. 튜플로 하면 두번째까지도 정렬되는 것을 잊..었다.. 열심히 구현했는데... 시간 초과도 안났네.. (반성)
참고

멋진.. 코드... 직접 구현하셨다..
공부하면 좋을 것 같아서 가져왔다..
문제가 된다면 연락주세요..죄송합니다

class heap:
    def __init__(self):
        self.dat=[]
        self.len=0
    def append(self,n):
        self.dat.append(n)
        le1=self.len
        le2=(le1-int(le1%2==0)-1)//2
        while le2>=0 and abs(self.dat[le2])>=abs(self.dat[le1]):
            if abs(self.dat[le2])>abs(self.dat[le1]) or self.dat[le2]>self.dat[le1]:
                self.dat[le1],self.dat[le2]=self.dat[le2],self.dat[le1]
                le1=le2
                le2 = (le1 - int(le1 % 2 == 0) - 1) // 2
            else:
                break
        self.len+=1
    def pop(self):
        result=self.dat[0]
        self.dat[0]=self.dat[-1]
        self.dat.pop()
        self.len-=1
        i=0
        while i*2+2<self.len:
            if abs(self.dat[i])>abs(self.dat[i*2+1]):
                if abs(self.dat[i])>abs(self.dat[i*2+2]):
                    if abs(self.dat[i*2+1])>abs(self.dat[i*2+2]):
                        self.dat[i],self.dat[i*2+2]=self.dat[i*2+2],self.dat[i]
                        i=i*2+2
                    elif abs(self.dat[i*2+2])>abs(self.dat[i*2+1]):
                        self.dat[i],self.dat[i*2+1]=self.dat[i*2+1],self.dat[i]
                        i=i*2+1
                    else:
                        if self.dat[i*2+1]<self.dat[i*2+2]:
                            self.dat[i], self.dat[i * 2 + 1] = self.dat[i * 2 + 1], self.dat[i]
                            i=i * 2 + 1
                        else:
                            self.dat[i], self.dat[i * 2 + 2] = self.dat[i * 2 + 2], self.dat[i]
                            i = i * 2 + 2
                else:
                    self.dat[i], self.dat[i * 2 + 1] = self.dat[i * 2 + 1], self.dat[i]
                    i=i*2+1

            elif abs(self.dat[i])<abs(self.dat[i*2+1]):
                if abs(self.dat[i])<abs(self.dat[i*2+2]):break
                elif abs(self.dat[i])>abs(self.dat[i*2+2]):
                    self.dat[i], self.dat[i * 2 + 2] = self.dat[i * 2 + 2], self.dat[i]
                    i=i*2+2
                else:
                    if self.dat[i]>self.dat[i*2+2]:
                        self.dat[i], self.dat[i * 2 + 2] = self.dat[i * 2 + 2], self.dat[i]
                        i = i * 2 + 2
                    else:
                        break
            else:
                if abs(self.dat[i]) < abs(self.dat[i * 2 + 2]):
                    if self.dat[i]>self.dat[i*2+1]:
                        self.dat[i], self.dat[i * 2 + 1] = self.dat[i * 2 + 1], self.dat[i]
                        i = i * 2 + 1
                    else:
                        break
                elif abs(self.dat[i])>abs(self.dat[i*2+2]):
                    self.dat[i], self.dat[i * 2 + 2] = self.dat[i * 2 + 2], self.dat[i]
                    i = i * 2 + 2
                else:
                    if self.dat[i]>self.dat[i*2+1]:
                        self.dat[i], self.dat[i * 2 + 1] = self.dat[i * 2 + 1], self.dat[i]
                        i = i * 2 + 1
                    elif self.dat[i]>self.dat[i*2+2]:
                        self.dat[i], self.dat[i * 2 + 2] = self.dat[i * 2 + 2], self.dat[i]
                        i = i * 2 + 2
                    else:
                        break
        if i*2+1<self.len:
            if (abs(self.dat[i])>abs(self.dat[i*2+1])) or (abs(self.dat[i])==abs(self.dat[i*2+1]) and self.dat[i]>self.dat[i*2+1]):
                self.dat[i], self.dat[i * 2 + 1] = self.dat[i * 2 + 1], self.dat[i]
        return result
abs_heap=heap()
from sys import stdin;input=stdin.readline
for _ in range(int(input())):
    n=int(input())
    if n==0:
        if abs_heap.len!=0:
            print(abs_heap.pop())
        else:
            print(0)
    else:
        abs_heap.append(n)

참고

이렇게 보다보니 힙을 직접 구현하는게 정답이지 않나.. 싶기도 하다.