kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_9_A: Complete Binary Tree

ここからヒープの話
ヒープというのは優先度付きキューを実現するための構造・・・らしい
あまり知らないゾーンに入ってきた

さてまずは完全二分木から
木と言ってるけど、完全二分木だと配列で書けるそうな
配列が1オリジンなんだけどどう書くのがすっきりするのかなあ
0番目は空けておくくらいかね

どういうものかよくわからないのでクラスとか作らずにベタに書こう
配列の何番目とかいう実装の詳細はいずれ隠蔽するはずのものだし

from math import floor

def parent_node(k):
    return k // 2

def left_node(k):
    return 2 * k

def right_node(k):
    return 2 * k + 1

def main():
    H = int(input())
    elems = [0] + [int(x) for x in input().split()]

    for k in range(1, H + 1):
        print("node {}: ".format(k), end="")
        print("key = {}, ".format(elems[k]), end="")
        if parent_node(k) >= 1:
            print("parent key = {}, ".format(
                elems[parent_node(k)]), end="")
        if left_node(k) <= H:
            print("left key = {}, ".format(
                elems[left_node(k)]), end="")
        if right_node(k) <= H:
            print("right key = {}, ".format(
                elems[right_node(k)]), end="")
        print()

main()

解答例もほとんど同じ