ALDS1_9の解答例(Python)

二分探索木に関する問題です． A,B,Cしかできていない上にコードが相当酷いですが，一応載せておきます． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_9_A: Complete Binary Tree

# ALDS1_9_A
def print_info(n,s):
    node = n+1
    key = s
    parent_key = (n+1)//2-1
    left_key = 2*n+1
    right_key = 2*n+2 
    print(f"node {node}: key = {key},",end=" ")
    # n==0 は親がないのでパス
    if n != 0:
        print(f"parent key = {S[parent_key]},",end=" ")
    if left_key < len(S):
        print(f"left key = {S[left_key]},",end=" ")
    if right_key < len(S):
        print(f"right key = {S[right_key]},",end=" ")
        
    print()

n = int(input())
S = input().split()

for i,s in enumerate(S):
    print_info(i,s)

2. ALDS1_9_B: Maximum Heap

# ALDS1_9_B
H = int(input())
A = list(map(int,input().split()))

def buildMaxHeap(A):
    for i in range(H//2+1):
        i = (H//2) - i
        maxHeapify(A,i)
        
def maxHeapify(A, i):
    l = 2*i+1 # 左のインデックス
    r = 2*i+2 # 右のインデックス
    largest = i # 最大ノードのインデックスをiで初期化
    # 左の子がi番目のノードより大きい場合
    if l < H:
        if A[i] < A[l]:
            largest = l
        
    # 左の子がi番目のノードより大きい場合
    if r < H:
        if A[largest] < A[r]:
            largest = r
          
    # ノードを入れ替える
    if largest != i:
        tmp = A[i]
        A[i] = A[largest]
        A[largest] = tmp
        maxHeapify(A, largest)
        
buildMaxHeap(A)
print(" ",end="")
print(*A)

3. ALDS1_9_C: Priority Queue

# ALDS1_9_C
import heapq

S = []
heapq.heapify(S)

while True:
    command = input().split(" ")
    if command[0] == "insert":
        heapq.heappush(S,-int(command[1])) # 最小のものしか取り出せないので符号を反転させる
    elif command[0] == "extract":
        x = heapq.heappop(S)
        print(-x) # 符号を直す
    else:
        break

4. ALDS1_9_D: Heap Sort

# ALDS1_9_D
# 編集中