[SWEA] 5177. [Python S/Wトラブルシューティング基本]8日間-バイナリヒップホップ[D 2]

📚 質問する

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVJ-_6qfsDFAWg#
バイナリ最小hipはheapq資料構造を用いることができる.しかし、heapqを直接実現することができます.
heapqのheappush()を実現する.
入力した値を最後にします.
次に、この数値を祖先ノードの値と比較し、祖先ノードがより大きい場合に変更します.
完全バイナリツリーを実現する際には,// 2演算を用いることに重点を置く.

📒 コード#コード#

def enq(num):   # 최소 힙에 값 넣기
    global last
    last += 1       # 최소 힙에 들어간 값의 개수를 세준다.
    min_heap[last] = num    # 맨 마지막에 값을 넣어준다.
    c = last
    p = c // 2
    while p > 0 and min_heap[p] > min_heap[c]:  # 조상이 더 크면 바꾼다.
        min_heap[p], min_heap[c] = min_heap[c], min_heap[p]
        c = p
        p = c // 2


t = int(input())
for tc in range(1, t + 1):
    n = int(input())
    arr = list(map(int, input().split()))
    last = 0
    min_heap = [0] * (n + 1)    # 최소 힙 배열
    for num in arr:             # 최소 힙에 입력을 다 넣어준다.
        enq(num)
    
    # 조상 노드의 합 구하기
    anc = last // 2             # 조상 노드
    total = 0                   # 조상 노드의 합
    while anc:
        total += min_heap[anc]  # 조상 노드의 값 더하기
        anc //= 2               # 더 상위의 조상 노드로
    print(f'#{tc} {total}')

🔍 結果:Pass