DA:graphtree

隣接リストと隣接行列

## 無向グラフ
# 隣接リスト
V = [[] for i in range(5)]

V[0] = [1, 3, 4]
V[1] = [0, 2]
V[2] = [1, 4]
V[3] = [0]
V[4] = [0, 2]

# 隣接行列
E = [
    [0, 1, 0, 1, 1],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0]
]


## 有向グラフ
# 隣接リスト
V = [[] for i in range(5)]

V[0] = [3]
V[1] = [0]
V[2] = [1]
V[4] = [0,2]

# 隣接行列
E = [
    [0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0]
]

ヒープ

# ヒープの中身を木構造っぽく表示する関数
def show(d=0):
    if 2 ** d > len(heap): return
    i = 2 ** d - 1
    j = 2 ** (d + 1) - 1
    print(heap[i:j])
    show(d+1)

# 新しい要素を挿入
def push(x):
    i = len(heap)
    heap.append(x)
    j = (i - 1) // 2
    while i > 0:
        if heap[i] > heap[j]:
            tmp = heap[i]
            heap[i] = heap[j]
            heap[j] = tmp
        i = j
        j = (i - 1) // 2

# 根を取り除いて最大値（元々の根が持っていた値）を返す関数
def pop():
    out = heap[0]
    x = heap.pop()  #注意：ここのpopはpythonのビルトイン関数であり，今実装しているpopとは違います．

    # ヒープが空っぽになったら，残りの処理は必要ないのでreturn
    if len(heap) == 0:
        return out

    heap[0] = x
    i = 0
    while True:
        # 左の子のインデックスを取得
        j = i ** 2 + 1

        # 左の子が存在しないなら，現在のiが葉であるため，それ以上入れ替える必要はない
        if ##### 埋めてください #####:
            break

        # 左の子が存在する場合，その値を取得しておく．
        y = ##### 埋めてください #####

        # 右の子(j+1)も存在していて，かつ左の子が持つ値よりも右の子が持つ値の方が大きい場合，
        # 右の子と親を比較する必要があるので，以下の処理を行う
        if ##### 埋めてください ##### and ##### 埋めてください #####:
            y = ##### 埋めてください #####
            j = ##### 埋めてください #####

        # 親の値と，二人の子のうちより大きな値を持つ方を比較して，子の値の方が大きければ，親子を入れ替える
        if ##### 埋めてください #####:
            ##### 埋めてください #####
        else:
            break
        i = j

    return out

# テスト
heap = []

push(19)
push(12)
push(15)
push(10)
push(7)
push(6)
push(1)
push(3)
push(7)
push(5)
push(3)
push(2)

push(20)
m = pop()
print('取得した最大値：', m)

print()
print('現在の木構造')
show()