ヒープと優先度キュー
最小値を取り出せる親子関係を、挿入と削除の途中経過から学びます。
説明
最小ヒープは、親の値が子の値以下になる木です。根が全体の最小値になりますが、兄弟同士や配列全体が昇順になっている必要はありません。木を隙間なく上から左へ詰め、配列で持つと、添字から親子を計算できます。
配列へ1を追加して根まで持ち上げ、その後、最小値を取り出して条件を修復します。最後にPythonのheapqで同じ処理を実行し、優先度が同じ仕事を受付順に処理する方法まで扱います。
1添字から親子を得る
添字iの左右の子は2i+1と2i+2です。根以外の親は(i-1)//2で求めます。まず親子の組と大小条件を表示します。
heap = [2, 5, 3, 9, 7]初期ヒープ; [(i, (i-1)//2, heap[(i-1)//2] <= heap[i]) for i in range(1, len(heap))]子・親・大小条件全てTrueなので最小ヒープの条件を満たします。配列の5の後に3がありますが問題ありません。順序条件があるのは各親子であり、隣り合う配列要素ではありません。
2末尾へ1を追加
木の形を崩さないよう末尾へ1を追加します。添字5の親は2で、値は3です。1の方が小さいため親子条件を破ります。
heap.append(1)末尾へ追加; child = len(heap)-1; parent = (child-1)//2子と親の添字; heap, (child, parent), heap[parent] <= heap[child]配置と条件配列末尾への追加だけではFalseとなります。次に親と入れ替えて、この違反を上へ移動させます。
3親と交換する
1と3を交換します。交換後の1は添字2で、まだ根2より小さいため、もう一度交換が必要です。
heap[2], heap[5] = heap[5], heap[2]1と3を交換; print(heap)1段上がった配置; heap[0], heap[2] = heap[2], heap[0]1と2を交換; print(heap)修復後の配置1が根になり、[1, 5, 2, 9, 7, 3]となりました。追加した場所から根への経路だけを直しています。全配列を整列する必要はありません。
4最小値を取り出す
根の1を取り出し、末尾の3を根へ移します。末尾を使うと木に途中の空きを作らずに済みます。
smallest = heap[0]最小値を保存; heap[0] = heap.pop()末尾を根へ移動; smallest, heap取得値と途中の配置取り出した値は1、根は3となりました。左右の子は5と2なので、根3は小さい子2と交換する必要があります。大きい子5と交換すると2との違反が残ります。
5小さい子と交換する
根3と右の子2を交換します。新しい位置の3には子がないため、修復はここで終わります。
heap[0], heap[2] = heap[2], heap[0]小さい子と交換; heap修復後の配置, all(heap[(i-1)//2] <= heap[i] for i in range(1, len(heap)))全親子の検査元の[2, 5, 3, 9, 7]へ戻り、全親子の条件はTrueです。取り出しでも根から葉へ向かう経路上だけを修復します。
6heapqで挿入・取り出し
ライブラリで同じ挿入と最小値の取り出しを行います。heappushとheappopが親子条件を保ちます。
import heapqヒープ操作; heapq.heappush(heap, 1)1を追加して修復; print(heap)追加後; smallest = heapq.heappop(heap)最小値を取得して修復; smallest, heap取得値と残り手順を追ったときと同じく1が取り出され、残りもヒープです。通常のlist.pop()は配列末尾を取る操作なので、最小値の取り出しにはheappopを使います。
7連続して最小値を取り出す
空になるまで現在の最小値を取り出します。配列自体は整列済みでなくても、取り出すたびに最小値を選べます。
ordered = [heapq.heappop(heap) for _ in range(len(heap))]全要素を最小値から取得; ordered, heap取得順と空のヒープ2・3・5・7・9の順で取り出せました。元のヒープは空です。参照だけならheap[0]で、heappopはデータを減らす操作です。
8同じ優先度では受付順
優先度の小さい仕事から処理します。同じ優先度の順序を固定するため、(優先度, 受付番号, 名前)で比較します。
jobs = [(2, 0, 'backup'), (1, 1, 'scan'), (1, 2, 'report')]優先度・受付番号・名前; heapq.heapify(jobs)リストをヒープに変換; [heapq.heappop(jobs) for _ in range(len(jobs))]優先順に取得scan・report・backupの順です。scanとreportは優先度1が同じなので、受付番号1と2で順序が決まります。ヒープの安定性に任せず、順序の条件をデータに含めています。
まとめ
最小ヒープでは親が子以下となり、根に最小値があります。配列全体の昇順とは異なります。
追加時は上へ、取り出し後は下へ必要な交換を行い、親子条件を復元します。
優先度が同じ場合の受付順は、比較対象に番号を含めて明示できます。
操作履歴と解説を振り返れます。
Python 3
heap = [2, 5, 3, 9, 7]; [(i, (i-1)//2, heap[(i-1)//2] <= heap[i]) for i in range(1, len(heap))][(1, 0, True), (2, 0, True), (3, 1, True), (4, 1, True)]
heap.append(1); child = len(heap)-1; parent = (child-1)//2; heap, (child, parent), heap[parent] <= heap[child]([2, 5, 3, 9, 7, 1], (5, 2), False)
heap[2], heap[5] = heap[5], heap[2]; print(heap); heap[0], heap[2] = heap[2], heap[0]; print(heap)[2, 5, 1, 9, 7, 3] [1, 5, 2, 9, 7, 3]
smallest = heap[0]; heap[0] = heap.pop(); smallest, heap(1, [3, 5, 2, 9, 7])
heap[0], heap[2] = heap[2], heap[0]; heap, all(heap[(i-1)//2] <= heap[i] for i in range(1, len(heap)))([2, 5, 3, 9, 7], True)
import heapq; heapq.heappush(heap, 1); print(heap); smallest = heapq.heappop(heap); smallest, heap[1, 5, 2, 9, 7, 3] (1, [2, 5, 3, 9, 7])
ordered = [heapq.heappop(heap) for _ in range(len(heap))]; ordered, heap([2, 3, 5, 7, 9], [])
jobs = [(2, 0, 'backup'), (1, 1, 'scan'), (1, 2, 'report')]; heapq.heapify(jobs); [heapq.heappop(jobs) for _ in range(len(jobs))][(1, 1, 'scan'), (1, 2, 'report'), (2, 0, 'backup')]
演習完了