Algorithms with Python

はじめに

今回は「二分木」と「ヒープ」を取り上げます。二分木は「木構造 (tree structer)」または「木 (tree)」と呼ばれるデータ構造の一つです。木は節 (ノード) と呼ばれる要素に対して、階層的な関係を表したものです。身近な例では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディレクトリ」があるように、木にも「根 (ルート)」と呼ばれる節が存在します。下図を見てください。

          図 1 : 一般的な木構造の一例

木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階層にある節を並べて書きます。根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木としての性質を持っています。これを「部分木」といいます。

木は、ある節からほかの節に至る「経路」を考えることができます。たとえば、A から J には、A - B - G - J という経路がありますね。これは、ディレクトリやファイルを指定するときのパスと同じです。

ある節から根の方向にさかのぼるとき、途中で通っていく節を「先祖」といい、直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」という関係になります。子を持たない節をとくに「葉」と呼ぶことがあります。上図でいうと、G は J, K の親で、J は G の子になります。J は子を持っていないので葉となります。

子は「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」といいます。また、順番がない木を「無順序木」と呼びます。節が持っている子の数を「次数」といいます。上図の場合、A は 3 つの子 B, C, D を持っているので、A の次数は 3 となります。すべての節の次数を n に揃えた順序木を「n 分木」と呼びます。とくに、次数が 2 の二分木は、プログラムでよく使われるデータ構造です。

               図 2 : 二分木の一例

上図に二分木の例を示します。二分木では、節に一つのデータを格納します。そして、その節の左側の子には小さいデータが、右側の子には大きいデータが配置されるように木を構成します。

この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木から 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどります。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つけることができます。

二分探索木の探索は新・お気楽 Python プログラミング入門第 2 回で説明した 二分探索 と同じ原理です。左右どちらかの子をたどるたびに、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が 15, 7, 3, 1 となり、最後に見つけることができました。

データ数を N とすると、単純な線形探索では平均で N / 2 回の比較が必要になりますが、二分探索木を使うと log₂ N 程度の回数で収まります。たとえば、データが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、二分探索木では 7 回程度の比較で済むわけです。

ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じになってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木 (balanced tree)」が考案されています。有名なところでは AVL 木、2 色木 (赤黒木)、2-3 木、B 木、B* 木などがあります。

●節の定義

それではプログラムを作りましょう。まず最初に、節を表すクラスを定義します。

リスト : 節の定義

class Node:
    def __init__(self, x):
        self.data  = x
        self.left  = None
        self.right = None

連結リストと違い、節を参照する変数が 2 つ必要になります。left が左側の子、right が右側の子を表します。子を持たない場合は、連結リストと同様に None をセットすることにします。連結リストのように、節を箱で表すと下図のようになります。

             図 3 : 二分木の構造

連結リストと同様に、ルートへの参照を変数 root に格納しておけば、この変数を使って二分木にアクセスすることができます。また、節が一つもない空の木は、変数 root に None をセットすれば表すことができます。なお、None のかわりに終端を表す節を用意する方法もあります。

今回は二分木の操作を関数として定義することにします。操作関数は一つのモジュールにまとめておいて、それを使って二分木を表すクラス BinaryTree を作ることにしましょう。

●データの探索

それでは、データを探索する関数 search() から作りましょう。次のリストを見てください。

リスト : データの探索

def search(node, x):
    while node:
        if node.data == x: return True
        if x < node.data:
            node = node.left
        else:
            node = node.right
    return False

関数 search() には節 node と探索するデータ x を渡します。node に格納されている data と x を比較し、値が等しければ True を返します。x が小さいのであれば左側の子をたどり、そうでなければ右側の子をたどります。たどるべき木がなくなれば node の値は None になるので、while ループを終了し False を返します。二分探索木の動作をそのままプログラムしているだけなので、難しいところはないと思います。

●データの挿入

次は、データを挿入する関数 insert() を作ります。search() は木を引数として受け取り、データを挿入した新しい木を返します。たとえば、変数 root に木が格納されている場合、データを挿入するときは次のように呼び出します。

root = insert(root, x)

この処理は再帰定義を使うと簡単にプログラムできます。次のリストを見てください。

リスト : データの挿入

def insert(node, x):
    if node is None: return Node(x)
    elif x == node.data: return node
    elif x < node.data:
        node.left = insert(node.left, x)
    else:
        node.right = insert(node.right, x)
    return node

最初に節 node が None かチェックします。そうであれば木は空なので、新しい節を Node(x) で生成して返します。たとえば、変数 root が None の場合、すなわち空の木であれば、新しい節が生成されて root にセットされます。

そうでなければ、x と node.data を比較します。x と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、何も行わずに node を返します。x が小さい場合は、左部分木に x を挿入します。ここで insert() を再帰呼び出しします。そして、その返り値を node.left にセットして node を返します。

たとえば、node.left が None の場合、再帰呼び出しの返り値は新しい節なので、それが node.left にセットされ、木にデータが挿入されたことになります。そして、新しいデータが挿入された木 (node) を返せばいいわけです。x が data よりも大きければ、同様に右部分木にデータを挿入します。

けっきょく、子を格納している節には、同じ子が再度セットされることになります。無駄なように思われるかもしれませんが、その分だけ簡単にプログラムを作ることができます。

●データの削除

次はデータを削除する処理を作りましょう。これは今までと違って少々面倒です。削除するデータが「葉」の場合は、それを削除するだけなので簡単ですが、木の途中のデータを削除する場合は、二分木の構成を崩さないように注意しないといけません。最初に、葉を削除する場合を説明します。下図を見てください。

               図 4 : データの削除（葉の場合）

15 を削除する場合を考えてみましょう。15 は「葉」にあたるので、それを削除するだけで大丈夫です。親の left に None を代入するだけです。

次に、子が一つある場合を考えてみましょう。

            図 5 : データの削除 (子が一つの場合)

16 を削除する場合、その子である 15 と置き換えれば二分探索木の構成は保たれます。これも簡単ですね。問題は、子が二つある節を削除する場合です。

            図 6 : データの削除 (子が二つの場合)

この場合、削除するデータの右部分木の中から最小値のデータ ^[*1] を探し、それと削除するデータと置き換えれば「右部分木 < 節 < 左部分木」の構成を崩さなくてすみます。上図で、14 を削除することを考えてみましょう。右部分木の中で 15 が最小値なので、それと 14 を置き換えます。そして、15 を格納していた節は削除します。節が最小値を格納している場合、その節の左側の子は存在しないので、その節を削除することは簡単です。

まず、木の中から最小値を探す関数と、最小値の節を削除する関数を作成しましょう。次のリストを見てください。

リスト : 最小値の探索と削除

# 最小値を探す
def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

# 最小値を削除する
def delete_min(node):
    if node.left is None: return node.right
    node.left = delete_min(node.left)
    return node

最小値は簡単に求めることができます。左側の子を順番にたどっていき、左側の子がない節に行き着いたとき、その節のデータが最小値になります。関数 search_min() は、最小値を求めてそれを返します。最初に、node.left の値をチェックします。もし、None であれば左側の子がないので、その節のデータが最小値です。return で node.data を返します。そうでなければ、search_min() を再帰呼び出しして左側の子をたどります。

関数 delete_min() は最小値を格納している節を削除します。node.left が None の節を探すのは search_min と同じです。見つけたら、もう一つの子 node.right を返します。これで、親の左部分木が書き換えられ、最小値を持つ節が削除されます。葉であれば node.right は None なので、単純に削除されることになります。

左側の子があれば delete_min() を再帰呼び出しして、その左部分木の中から最小値を探し出して削除します。次に、その返り値を node.left にセットして、return で node を返します。

それでは、データを削除する関数 delete() を作ります。まず削除するデータを探索して、見つけたら子の有無に合わせた削除処理を行います。

リスト : 削除
def delete(node, x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left, x)
        else:
            node.right = delete(node.right, x)
    return node

まず、node が None ならば木は空なので、何もしないで node を返します。削除するデータが見つからない場合や空の木を与えた場合がこれに相当します。次に、削除するデータ x と node.data を比較し、等しい場合はその節を削除します。node.left が None の場合は node.right を返し、node.right が None の場合は node.left を返します。

子が 2 つある場合は、右部分木の最小値を search_min() で求め、node.data の値を書き換えます。そして、delete_min() で最小値を格納していた節を削除します。これで、削除するデータを最小値で置き換え、不要になった節を二分木から削除することができます。x と data が等しくない場合は、左右の部分木をたどって削除するデータを探索します。この処理は今までと同じです。最後に node を返します。

●巡回 (traverse)

最後に、二分木の全データにアクセスする関数を作りましょう。二分木はデータの大小関係を使って構成されているので、ある順番で節をすべて出力すると、それはソートした結果と同じになります。「木」のすべての節を規則的な順序で回ることを「巡回 (traverse)」といいいます。このなかで、次の 3 つの方法が重要です。

1. 行きがけ順
   まず節のデータを出力、その後左の子、右の子の順番で出力する。
2. 帰りがけ順
   左の子、右の子と出力してから、節のデータを出力する。
3. 通りがけ順
   左の子を出力、次に節のデータを出力、最後に右の子を出力する。

名前の由来は、節のデータを出力するタイミングからきています。節に最初に到達したときに出力する方法が「行きがけ」、子を出力してその節に戻ってきたときに出力する方法が「帰りがけ」、子を出力する途中でその節に戻ってきたときに出力する方法が「通りがけ」です。

二分木は「左の子 < 節のデータ < 右の子」という関係が成り立つので、通りがけ順に出力すれば、ソートされた出力結果を得ることができます。この処理も、再帰定義を使えば簡単に実現できます。次のリストを見てください。

リスト : 木の巡回

# 高階関数バージョン
def traverse_h(func, node):
    if node:
        traverse_h(func, node.left)
        func(node.data)
        traverse_h(func, node.right)

# ジェネレータバージョン
def traverse(node):
    if node:
        for x in traverse(node.left):
            yield x
        yield node.data
        for x in traverse(node.right):
            yield x

関数 traverse_h() は高階関数で、通りがけ順で木を巡回し、データに関数 func を適用します。node が None でなければ、再帰呼び出しで左部分木を巡回してから func(nod.data) を実行し、そのあとで右部分木を巡回します。

また、Python のジェネレータを使うと関数 traverse() のようになります。Python の場合、こちらの方が便利かもしれません。ジェネレータについては拙作のページ 新・お気楽 Python プログラミング入門第 2 回 で説明しています。よろしければ参考にしてください。

●BinaryTree クラスの作成

これらの操作関数を一つのファイル、たとえば node.py にまとめておきます。Python の場合、このファイルをモジュールとして利用することができます。モジュールについては拙作のページ 新・お気楽 Python プログラミング入門第 2 回 を参考にしてください。モジュール node を使うと、二分木を表すクラス BinaryTree は次のようになります。

リスト : 二分木

import node

class BinaryTree:
    def __init__(self):
        self.root = None

    # 探索
    def search(self, x):
        return node.search(self.root, x)

    # 挿入
    def insert(self, x):
        self.root = node.insert(self.root, x)

    # 削除
    def delete(self, x):
        self.root = node.delete(self.root, x)

    # 巡回
    def traverse(self):
        for x in node.traverse(self.root):
            yield x

BinaryTree のインスタンス変数は root で、これが二分木の根 (ルート) になります。あとは、メソッドの処理に対応する関数を呼び出すだけです。なお、BinaryTree を表示するメソッド __str__() は説明を割愛しました。詳細は プログラムリスト１ をお読みください。

●実行例

それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。

# テスト
if __name__ == '__main__':
    import random
    tree = BinaryTree()
    data = [random.randint(0, 100) for x in range(10)]
    print(data)
    print(tree)
    for x in data: tree.insert(x)
    print(tree)
    for x in data:
        print('search', x, tree.search(x))
        print('delete', x)
        tree.delete(x)
        print('search', x, tree.search(x))
        print(tree)

実行結果を示します。

$ python3 bintree.py
[32, 28, 1, 5, 37, 99, 19, 54, 31, 52]
BinaryTree()
BinaryTree(1, 5, 19, 28, 31, 32, 37, 52, 54, 99)
search 32 True
delete 32
search 32 False
BinaryTree(1, 5, 19, 28, 31, 37, 52, 54, 99)
search 28 True
delete 28
search 28 False
BinaryTree(1, 5, 19, 31, 37, 52, 54, 99)
search 1 True
delete 1
search 1 False
BinaryTree(5, 19, 31, 37, 52, 54, 99)
search 5 True
delete 5
search 5 False
BinaryTree(19, 31, 37, 52, 54, 99)
search 37 True
delete 37
search 37 False
BinaryTree(19, 31, 52, 54, 99)
search 99 True
delete 99
search 99 False
BinaryTree(19, 31, 52, 54)
search 19 True
delete 19
search 19 False
BinaryTree(31, 52, 54)
search 54 True
delete 54
search 54 False
BinaryTree(31, 52)
search 31 True
delete 31
search 31 False
BinaryTree(52)
search 52 True
delete 52
search 52 False
BinaryTree()

●ヒープ

「ヒープ (heap)」は「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きい、という関係を満たすように作ります。「半順序木」の場合、親は子より小さいか等しい、という関係を満たすように作ります。したがって、木の根（配列の添字 0）には、必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。

      図 7 : ヒープと配列の対応関係

ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (N) の対数 (log₂ N) に比例する程度の時間で済みます。

●ヒープの構築 (1)

ヒープは、次の手順で作ることができます。

TABLE [＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     最初は空

      [80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     最初のデータをセット

      [80 10 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     次のデータをセットし親と比較
       親 子                              親の位置 0 = (1 - 1)/2

      [10 80 ＊ ＊ ＊ ＊ ＊ ＊ ＊ ＊]     順序が違っていたら交換

      [10 80 60 ＊ ＊ ＊ ＊ ＊ ＊ ＊]     データをセットし比較
       親    子                           親の位置 0 = (2 - 1)/2

      [10 80 60 20 ＊ ＊ ＊ ＊ ＊ ＊]     データをセットし比較
          親    子                        親の位置 1 = (3 - 1)/2

      [10 20 60 80 ＊ ＊ ＊ ＊ ＊ ＊]     交換する

      ・・・・データがなくなるまで繰り返す・・・・

                図 8 : ヒープの構築 (1)

まず、データを最後尾に追加します。そして、このデータがヒープの条件を満たしているかチェックします。もしも、条件を満たしていなければ、親と子を入れ換えて、次の親をチェックします。これを木のルート方向 (添字 0 の方向) に向かって繰り返します。条件を満たすか、木のルート (添字 0) まで到達すれば、処理を終了します。これをデータの個数だけ繰り返します。このアルゴリズムを Python でプログラムすると、次のようになります。

リスト : ヒープの構築

def upheap(buff, n):
    while True:
        p = (n - 1) // 2
        if p < 0 or buff[p] <= buff[n]: break
        temp = buff[n]
        buff[n] = buff[p]
        buff[p] = temp
        n = p

関数 upheap() はヒープを満たすように n 番目の要素をルート方向に向かって移動させます。0 から n - 1 番目までの要素はヒープの条件を満たしているとします。n の親を p とすると、p は (n - 1) // 2 で求めることができます。

そして、p が 0 より小さい、または buff[p] <= buff[n] であればヒープの条件を満たすので、break で処理を終了します。そうでなければ、buff[p] と buff[n] を交換して、次の親子関係をチェックします。

あとは、配列の最後尾にデータを追加して、upheap() を呼び出せばいいわけです。また、データが格納されている配列でも、upheap() を適用してヒープを構築することができます。

for x in range(1, len(buff)):
    upheap(buff, x)

ただし、この方法はデータ数を n とすると upheap() を n - 1 回呼び出すため、それほど速い方法ではありません。もう少し高速な方法はあとで説明することにしましょう。

●ヒープの再構築

次に、最小値を取り出したあとで新しいデータを追加し、ヒープを再構築する手順を説明します。

TABLE [10 20 30 40 50 60 70 80 90 100]    ヒープを満たしている

      [＊ 20 30 40 50 60 70 80 90 100]    最小値を取り出す

      [66 20 30 40 50 60 70 80 90 100]    新しい値をセット

      [66 20 30 40 50 60 70 80 90 100]    小さい子と比較する
       ^  ^                               (2*0+1) < (2*0+2)
       親 子 子

      [20 66 30 40 50 60 70 80 90 100]    交換して次の子と比較
          ^     ^                         (2*1+1) < (2*1+2)
          親    子 子

      [20 40 30 66 50 60 70 80 90 100]    交換して次の子と比較
                ^        ^                (2*3+1) < (2*3+2)
                親       子 子            親が小さいから終了

                図 9 : ヒープの再構築

最初に、ヒープの最小値である添字 0 の位置にあるデータを取り出します。次に、その位置に新しいデータをセットし、ヒープの条件を満たしているかチェックします。ヒープの構築とは逆に、葉の方向 (添字の大きい方向) に向かってチェックしていきます。

まず、2 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。このアルゴリズムを Python でプログラムすると次のようになります。

リスト : ヒープの再構築

def downheap(buff, n):
    size = len(buff)
    while True:
        c = 2 * n + 1
        if c >= size: break
        if c + 1 < size:
            if buff[c] > buff[c + 1]: c += 1
        if buff[n] <= buff[c]: break
        temp = buff[n]
        buff[n] = buff[c]
        buff[c] = temp
        n = c

関数 downheap() はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。最初に配列 buff の大きさを求めて変数 size にセットします。次に、n の子 c を求めます。これが size よりも大きければ処理を終了します。

そして、もう一つの子 (c + 1) がある場合は、小さい子を選択します。そして、buff[n] <= buff[c] が真であれば、ヒープの条件を満たしているので、break で処理を終了します。そうでなければ、n 番目と c 番目の要素を交換して処理を繰り返します。

最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 buff の最後尾のデータを buff[0] にセットしてヒープを再構築します。上図の例でいえば、100 を buff[0] にセットして、ヒープを再構築すればいいわけです。この場合、ヒープに格納されているデータの個数は一つ減ることになります。

●ヒープの構築 (2)

ところで、n 個のデータをヒープに構築する場合、n - 1 回 upheap を呼び出さなければいけません。ところが、すべてのデータを配列に格納したあと、ヒープを構築するうまい方法があります。次の図を見てください。

TABLE [100 90 80 70 60|50 40 30 20 10]    後ろ半分が葉に相当

      [100 90 80 70|60 50 40 30 20 10]    60 を挿入する
                    ^
      [100 90 80 70|60 50 40 30 20 10]    子供と比較する
                    ^              ^       (2*4+1), (2*4+2)
                    親             子

      [100 90 80 70|10 50 40 30 20 60]    交換する

      ・・・ 70 80 90 を順番に挿入し修正する ・・・

      [100|10 40 20 60 50 80 30 70 90]    90 を挿入し修正した

      [100 10 40 20 60 50 80 30 70 90]    100 を挿入、比較
        ^  ^  ^                           (2*0+1), (2*0+2)
        親 子 子

      [10 100 40 20 60 50 80 30 70 90]    小さい子と交換し比較
           ^     ^  ^                     (2*1+1), (2*1+2)
           親    子 子

      [10 20 40 100 60 50 80 30 70 90]    小さい子と交換し比較
                 ^           ^  ^         (2*3+1), (2*3+2)
                 親          子 子

      [10 20 40 30 60 50 80 100 70 90]    交換して終了

                図 10 : ヒープの構築 (2)

配列を前半と後半の 2 つに分けると、後半部分はこれより下にはデータが繋がっていない葉の部分になります。つまり、後半部分の要素は互いに関係がなく、前半部分の枝にあたる要素と関係しているだけでなのです。したがって、後半部分だけを見れば、それはヒープを満たしていると考えることができます。

あとは、前半部分の要素に対して、葉の方向に向かってヒープの関係を満たすよう修正していけば、配列全体がヒープを満たすことになります。この処理は downheap() を使うと次のように簡単にプログラムできます。

for x in range(len(buff) // 2 - 1, -1, -1):
    downheap(buff, x)

後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。

●優先度つき待ち行列

それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。

優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。Python には配列をヒープとして扱うモジュール heapq がありますが、本稿ではクラスとして実装してみましょう。クラス名は PQueue とします。定義するメソッドを表に示します。

メソッド名は enqueue, dequeue としてもよかったのですが、モジュール heapq の関数が heappush, heappop になっているので、このプログラムでは push, pop としました。また、データを追加する関数を insert とし、最小値を取り出す関数を delete_min としている参考文献もあります。

プログラムは次のようになります。

class PQueue:
    def __init__(self, buff = []):
        self.buff = buff[:]
        for n in range(len(self.buff) // 2 - 1, -1, -1):
            _downheap(self.buff, n)

    # データの追加
    def push(self, data):
        self.buff.append(data)
        _upheap(self.buff, len(self.buff) - 1)

    # 最小値を取り出す
    def pop(self):
        if len(self.buff) == 0: raise IndexError
        value = self.buff[0]
        last = self.buff.pop()
        if len(self.buff) > 0:
            # ヒープの再構築
            self.buff[0] = last
            _downheap(self.buff, 0)
        return value

メソッド __init__() は、引数の配列 buff をコピーして、インスタンス変数 buff にセットします。そして、関数 _downheap() を呼び出してヒープを構築します。downheap と upheap は内部で使う関数なので、名前にアンダーバーを付けました。データを追加するメソッド push() は簡単です。append() で配列 buff の最後にデータ x を追加し、_upheap() を呼び出してヒープに挿入します。

次は、最小値を取り出すメソッド pop() を説明します。pop() はデータがなければエラー IndexError を送出します。それから、最小値 self.buff[0] を取り出して変数 value にセットし、最後尾のデータを pop() で取り出して変数 last にセットします。もし、配列 buff にデータが残っていたならば、last を self.buff[0] にセットして _downheap() でヒープを再構築します。最後に return で最小値 value を返します。

メソッド peek() と isEmpty() は簡単なので説明を割愛いたします。詳細は プログラムリスト２ をお読みください。

●実行例

それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。

# 簡単なテスト
if __name__ == '__main__':
    import random
    a = PQueue()
    for x in range(10):
        n = random.randint(0, 100)
        a.push(n)
        print(n, 'min data = ', a.peek())
    while not a.isEmpty():
        print(a.pop(), end=' ')
    print()
    data = [random.randint(0, 100) for x in range(10)]
    print(data)
    a = PQueue(data)
    while not a.isEmpty():
        print(a.pop(), end=' ')
    print()

実行結果は次のようになります。

$ python3 pqueue.py
63 min data =  63
12 min data =  12
24 min data =  12
18 min data =  12
27 min data =  12
24 min data =  12
8 min data =  8
1 min data =  1
45 min data =  1
94 min data =  1
1 8 12 18 24 24 27 45 63 94
[100, 84, 97, 73, 74, 92, 100, 61, 64, 86]
61 64 73 74 84 86 92 97 100 100

●プログラムリスト１

#
# node.py : 二分木の節と操作関数の定義
#
#           Copyright (C) 2006-2022 Makoto Hiroi
#

# 節の定義
class Node:
    def __init__(self, x):
        self.data  = x
        self.left  = None
        self.right = None

# 探索
def search(node, x):
    while node:
        if node.data == x: return True
        if x < node.data:
            node = node.left
        else:
            node = node.right
    return False

# 挿入
def insert(node, x):
    if node is None: return Node(x)
    elif x == node.data: return node
    elif x < node.data:
        node.left = insert(node.left, x)
    else:
        node.right = insert(node.right, x)
    return node

# 最小値を探す
def search_min(node):
    if node.left is None: return node.data
    return search_min(node.left)

# 最小値を削除する
def delete_min(node):
    if node.left is None: return node.right
    node.left = delete_min(node.left)
    return node

# 削除
def delete(node, x):
    if node:
        if x == node.data:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data:
            node.left = delete(node.left, x)
        else:
            node.right = delete(node.right, x)
    return node

# 巡回

# 高階関数バージョン
def traverse_h(func, node):
    if node:
        traverse_h(func, node.left)
        func(node.data)
        traverse_h(func, node.right)

# ジェネレータバージョン
def traverse(node):
    if node:
        for x in traverse(node.left):
            yield x
        yield node.data
        for x in traverse(node.right):
            yield x

#
# bintree.py : 二分探索木
#
#              Copyright (C) 2006-2022 Makoto Hiroi
#
import node

# 二分木
class BinaryTree:
    def __init__(self):
        self.root = None

    # 探索
    def search(self, x):
        return node.search(self.root, x)

    # 挿入
    def insert(self, x):
        self.root = node.insert(self.root, x)

    # 削除
    def delete(self, x):
        self.root = node.delete(self.root, x)

    # 巡回
    def traverse(self):
        for x in node.traverse(self.root):
            yield x

    # 表示
    def __str__(self):
        if self.root is None: return 'BinaryTree()'
        buff = 'BinaryTree('
        for x in node.traverse(self.root):
            buff += '%s, ' % x
        buff = buff.rstrip(',  ')
        buff += ')'
        return buff

# テスト
if __name__ == '__main__':
    import random
    tree = BinaryTree()
    data = [random.randint(0, 100) for x in range(10)]
    print(data)
    print(tree)
    for x in data: tree.insert(x)
    print(tree)
    for x in data:
        print('search', x, tree.search(x))
        print('delete', x)
        tree.delete(x)
        print('search', x, tree.search(x))
        print(tree)

●プログラムリスト２

#
# pqueue.py : 優先度つき待ち行列
#
#             Copyright (C) 2006-2022 Makoto Hiroi
#

# 葉の方向へ
def _downheap(buff, n):
    size = len(buff)
    while True:
        c = 2 * n + 1
        if c >= size: break
        if c + 1 < size:
            if buff[c] > buff[c + 1]: c += 1
        if buff[n] <= buff[c]: break
        temp = buff[n]
        buff[n] = buff[c]
        buff[c] = temp
        n = c

# 根の方向へ
def _upheap(buff, n):
    while True:
        p = (n - 1) // 2
        if p < 0 or buff[p] <= buff[n]: break
        temp = buff[n]
        buff[n] = buff[p]
        buff[p] = temp
        n = p

class PQueue:
    def __init__(self, buff = []):
        self.buff = buff[:]   # コピー
        for n in range(len(self.buff) // 2 - 1, -1, -1):
            _downheap(self.buff, n)

    # データの追加
    def push(self, data):
        self.buff.append(data)
        _upheap(self.buff, len(self.buff) - 1)

    # 最小値を取り出す
    def pop(self):
        if len(self.buff) == 0: raise IndexError
        value = self.buff[0]
        last = self.buff.pop()
        if len(self.buff) > 0:
            # ヒープの再構築
            self.buff[0] = last
            _downheap(self.buff, 0)
        return value

    # 最小値を求める
    def peek(self):
        if len(self.buff) == 0: raise IndexError
        return self.buff[0]

    # 空か
    def isEmpty(self): return len(self.buff) == 0

# テスト
if __name__ == '__main__':
    import random
    a = PQueue()
    for x in range(10):
        n = random.randint(0, 100)
        a.push(n)
        print(n, 'min data = ', a.peek())
    while not a.isEmpty():
        print(a.pop(), end=' ')
    print()
    data = [random.randint(0, 100) for x in range(10)]
    print(data)
    a = PQueue(data)
    while not a.isEmpty():
        print(a.pop(), end=' ')
    print()