[SWEA] 2930. 힙(python)

📌문제

💪아이디어

1. max heap구현
   max heap은 부모 노드가 왼쪽, 오른쪽 서브트리의 노드들보다 큰 완전 이진 트리이다. 완전 이진 트리는 마지막 트리의 height를 제외하고 노드가 모두 존재하고 마지막 height에는 왼쪽부터 노드가 차있으며 leaf노드는 마지막 height에만 존재한다.
   
   • add
     max heap에 노드를 추가하면 가장 마지막 인덱스에 추가된다. 추가한 인덱스와 부모노드와 비교해서 부모 노드가 더 크면 max heap상태라 판단하고 heapify를 멈춘다. 부모 노드가 더 작으면 부모 노드를 아래로 내리고 해당 인덱스를 부모 노드 자리로 옮긴 후 (부모노드가 더 클떄 or root)까지 heapify를 반복한다.
     
     
   • delete
     max heap에 노드를 삭제하면 root에 있는 값을 반환하고 마지막 노드를 root노드 자리로 옮긴다.
     
   • heapify
     루트노드에서부터 왼쪽, 오른쪽 자식 노드보다 작으면 왼쪽, 오른쪽 자식노드 중 더 큰 자식노드 자리로 옮긴다. 자식노드보다 클때까지 반복한다. 자식 노드가 없을 수도 있으니 자식노드의 여부도 체크해야한다.
     
     

🥂코드

class max_heap:
    def __init__(self):
        self.queue=[]

    def parent(self,index):
        return (index-1)//2
    
    def left_child(self,index):
        return index*2+1
    
    def right_child(self,index):
        return index*2+2
    
    def swap_node(self,inx,parent):
        self.queue[inx],self.queue[parent]=self.queue[parent],self.queue[inx]

    def add_node(self,node):
        self.queue.append(node)
        last = len(self.queue)-1
        while last>=0:
            parent = self.parent(last)
            if  parent>=0 and self.queue[parent]<self.queue[last]:
                self.swap_node(last,parent)
                last = parent
            else: break

    def delete_node(self):
        last = len(self.queue)-1
        if last<0: 
            return '-1 '
        self.swap_node(last,0)
        max_val = self.queue.pop()
        self.max_heapify(0)
        return '{} '.format(max_val)
    
    def max_heapify(self,inx):
        left,right = self.left_child(inx),self.right_child(inx)
        max_inx = inx
        
        if left<len(self.queue) and self.queue[left]>self.queue[max_inx]:
            max_inx=left
        if right<len(self.queue) and self.queue[right]>self.queue[max_inx]:
            max_inx=right
        
        if max_inx!=inx:
            self.swap_node(inx,max_inx)
            self.max_heapify(max_inx)

T=int(input())
answer=[]
for tc in range(1,T+1):
    tmp='#{} '.format(tc)
    n=int(input())
    heap = max_heap()
    for _ in range(n):
        cal = list(map(int,input().split()))
        if cal[0]==1:
            heap.add_node(cal[1])
        else:
            tmp+=heap.delete_node()
    answer.append(str(tmp))

for a in answer:
    print(a)