次にやる仕事を、すぐ選ぶ
ヒープとは、一番小さい値を、いつもすぐ取り出せるように並べた木です。優先度の高い仕事から順に取り出す、優先度付きキューを作れるようになります。
make は、bison で文法を作り、次に flex、最後に gcc を動かします。先にすべき仕事が決まっているとき、次の仕事を選ぶたびに全部を並べ直すのは無駄です。
このレッスンのゴール
メモ
ヒープを使って、一番小さい値をいつも手元に置くことができる。
重要な言葉
| ことば | いみ |
|---|---|
| ヒープ | 親が子より大きくない決まりを守る木 |
| 優先度付きキュー | 優先度の高いものから、先に出るキュー |
| 親と子 | 木の上のノードと、その下に直接つながるノード |
| 上へ上げる | 新しい要素を、親と入れ替えて上へ動かすこと |
| 下へ下げる | 根の要素を、子と入れ替えて下へ動かすこと |
学生が入力するセルは、このプレビューでは空白です。
ヒープは、親が子より大きくない
最小ヒープでは、どの親も、2つの子以下の値です。だから、一番小さい値は、いつも根にあります。
左の子と右の子の大小は、決まっていません。決まりは、親と子の間だけです。木は、リストに隙間なく詰めて持てます。
例: リストに詰めたヒープ
| 添字 | 値 | 親の添字 | 子の添字 |
|---|---|---|---|
| 0 | 1 | なし | 1 と 2 |
| 1 | 4 | 0 | 3 と 4 |
| 2 | 2 | 0 | 5 |
| 3 | 9 | 1 | なし |
| 4 | 5 | 1 | なし |
| 5 | 3 | 2 | なし |
学生が入力するセルは、このプレビューでは空白です。
添字5の親と、5の子の添字
python3 -c "print((5 - 1) // 2, 2 * 5 + 1, 2 * 5 + 2)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
新しい要素は後ろに入れて、上へ上げる
push では、まず新しい要素を一番後ろに入れます。そこは、リストの終わりなので、ずらす要素はありません。
そのあと、親と比べます。親のほうが大きければ入れ替え、1つ上へ進みます。親が小さいか同じになったら、止まります。入れ替えは、木の高さまでです。
例: [1, 4, 3, 9, 5] に2を入れる
| 手順 | したこと | リストの様子 |
|---|---|---|
| 1 | 後ろに2を入れる | [1, 4, 3, 9, 5, 2] |
| 2 | 親の3より小さいので入れ替える | [1, 4, 2, 9, 5, 3] |
| 3 | 親の1は2以下なので止まる | [1, 4, 2, 9, 5, 3] |
学生が入力するセルは、このプレビューでは空白です。
上へ上げるコード
heap = [1, 4, 3, 9, 5]
heap.append(2) # まず、一番後ろに入れます。
i = len(heap) - 1
swaps = 0
while i > 0:
parent = (i - 1) // 2
if heap[parent] <= heap[i]:
break # 親が小さいか同じなら、そこで止まります。
temp = heap[parent]
heap[parent] = heap[i]
heap[i] = temp
swaps = swaps + 1
i = parent
print(heap, "入れ替えた回数:", swaps)
# 2 を 0 に変えて、もう一度実行しましょう。
取り出したら、最後の要素を根から下げる
pop では、根の要素が答えです。取り出したあとの空いた根には、リストの最後の要素を移します。
そのあと、2つの子のうち小さいほうと比べます。子のほうが小さければ入れ替え、1つ下へ進みます。子より小さくなったら、止まります。
例: [1, 4, 2, 9, 5, 3] から取り出す
| 手順 | したこと | リストの様子 |
|---|---|---|
| 1 | 根の1を取り出す。最後の3を根へ | [3, 4, 2, 9, 5] |
| 2 | 子の4と2のうち、小さい2と入れ替える | [2, 4, 3, 9, 5] |
| 3 | 3に子はないので止まる | [2, 4, 3, 9, 5] |
学生が入力するセルは、このプレビューでは空白です。
下へ下げるコード
heap = [1, 4, 2, 9, 5, 3]
smallest = heap[0]
heap[0] = heap.pop() # 最後の要素を根に移します。
i = 0
while True:
left = 2 * i + 1
right = 2 * i + 2
small = i
if left < len(heap) and heap[left] < heap[small]:
small = left
if right < len(heap) and heap[right] < heap[small]:
small = right
if small == i:
break # 子より小さいので、ここに落ち着きます。
temp = heap[i]
heap[i] = heap[small]
heap[small] = temp
i = small
print(smallest, heap)
# 先頭を [2, 4, 3, 9, 5] から始めて、結果を予想しましょう。
標準の heapq で、小さい順に取り出す
python3 -c "import heapq; h = []; heapq.heappush(h, 5); heapq.heappush(h, 1); heapq.heappush(h, 3); print(heapq.heappop(h), heapq.heappop(h), heapq.heappop(h))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
優先度の小さい仕事が先に出る
python3 -c "import heapq; h = [(2, 'flex'), (1, 'bison'), (3, 'gcc')]; heapq.heapify(h); print(heapq.heappop(h))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
ヒープのリストは、全部が小さい順に並んでいると思いがちです。[1, 4, 2, 9, 5, 3] は、2番目が4で、3番目が2です。決まっているのは親と子の間だけで、取り出したときに初めて小さい順に出ます。