Tree - 이진 힙

정렬된 값들을 저장할 리스트(tree)와 크기비교를 위해 idx를 생성해준다.

tree가 1에서부터 N까지 차근차근(정렬을 생각하지 않고 단순 입력된 대로) 값을 넣어주는 인덱스의 역할을 한다면
chk는 부모노드와 자식노드를 비교하는 역할이다.
chk가 1을 넘어가면(루트 노드가 아니면) 부모노드(chk//2)와 비교하는 과정을 추가해준다.

for tc in range(1,int(input())+1):
    N = int(input())
    arr=list(map(int, input().split()))
    tree=[0]*(N+1)
    idx=1
    
    for i in range(N):
        tree[idx]=arr[i]
        chk= idx
        while chk>1:
            if tree[chk]<=tree[chk//2]:
                tree[chk],tree[chk//2]= tree[chk//2], tree[chk]
            chk//=2
        idx+=1
    
    
    summ=0
    fin = N
    while fin>0:
        fin//=2
        summ+=tree[fin]
    
    print(f'#{tc} {summ}')

텍스트!