Python のバイナリ ヒープの詳細な紹介 (コード例)

この記事では、Python のバイナリ ヒープについて詳しく紹介 (コード例) しています。一定の参考値があります。困っている友人は参考にしてください。お役に立てれば幸いです。

1. ヒープ

データ構造 ヒープは優先キューです。キューは先入れ先出しのデータ構造です。キューの重要な変形は、優先キューと呼ばれます。優先キューを使用すると、任意の順序でオブジェクトを追加でき、いつでも (おそらくオブジェクトの追加中に) 最小の要素を検索 (または削除) できるため、Python の min メソッドよりも効率的です。
優先キューでは、キュー内のアイテムの論理順序は優先度によって決まります。最も優先度の高いアイテムはキューの先頭にあり、最も低い優先度のアイテムはキューの後ろにあります。したがって、項目を優先キューに入れると、新しい項目が先頭に移動し続ける可能性があります。

2. バイナリ ヒープの操作

バイナリ ヒープ実装の基本的な操作は次のとおりです:

BinaryHeap() は新しい空のバイナリを作成しますヒープ。
insert(k) 新しい項目をヒープに追加します。
findMin() は、最小のキー値を持つ項目を返し、その項目をヒープ内に残します。
delMin() ヒープから項目を削除して、最小のキー値を持つ項目を返します。
ヒープが空の場合、isEmpty() は true を返し、それ以外の場合は false を返します。
size() はヒープ内のアイテムの数を返します。
buildHeap(list) キーのリストから新しいヒープを構築します。

アイテムをヒープに追加する順序に関係なく、毎回最小のアイテムが削除されることに注意してください。

ヒープを効率的に機能させるために、バイナリ ツリーの対数的性質を利用してヒープを表現します。対数パフォーマンスを保証するには、ツリーのバランスを保つ必要があります。 Balanced Binary Tree ルートの左右のサブツリーにほぼ同じ数のノードがあり、空の木であるか、左右のサブツリーの高さの差の絶対値が 1 を超えません。 、左右のサブツリーのノード数はほぼ同じであり、サブツリーはすべてバランスのとれた二分木です。ヒープ実装では、完全なバイナリ ツリー を作成することでツリーのバランスを保ちます。完全な二分木は、各レベルのノードが完全に満たされているツリーであり、最後のレベルが満たされていない場合は、右側のいくつかのノードだけが欠落しています。図 1 は、完全なバイナリ ツリーの例を示しています。
完全なバイナリ ツリーのもう 1 つの興味深い特性は、単一のリストを使用してそれを表現できることです。

# from pythonds.trees.binheap import BinHeap
class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    def insert(self,k):
        '''将项附加到列表的末尾，并通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 '''
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
    def buildHeap(self, alist):
        '''直接将整个列表生成堆，将总开销控制在O(n)'''
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本
        while (i > 0):
            self.percDown(i)
           i = i - 1
    def percUp(self,i):
        '''如果新添加的项小于其父项，则我们可以将项与其父项交换。'''
        while i // 2 > 0:    # // 取整除 - 返回商的整数部分（向下取整）
            if self.heapList[i] < self.heapList[i//2]:
               tmp = self.heapList[i // 2]
               self.heapList[i // 2] = self.heapList[i]
               self.heapList[i] = tmp
            i = i // 2
    def percDown(self, i):
        &#39;&#39;&#39;将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。&#39;&#39;&#39;
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc
    def minChild(self, i):
        &#39;&#39;&#39;在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。&#39;&#39;&#39;
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1
    def delMin(self):
        &#39;&#39;&#39;移走根节点的元素（最小项）后如何保持堆结构和堆次序&#39;&#39;&#39;
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

バイナリ ヒープに関する最後の部分は、順序なしリストから「ヒープ」を生成する方法を見つけることです。最初に考えられるのは、順序なしリストの各要素を順番にヒープに挿入することです。ソートされたリストの場合、二分検索を使用して適切な位置を見つけ、O(logn) の時間計算量でヒープの次の位置にキー値を挿入できます。さらに、リストに要素を挿入するには、新しいノード用のスペースを確保するためにリストの他の要素を移動する必要があり、時間計算量は O(n) です。したがって、挿入メソッドを使用する総コストは O(nlogn) です。実際、リスト全体をヒープに直接生成し、総オーバーヘッドを O(n) に制御できます。リスト 6 は、ヒープを生成する操作を示しています。

O(n) のオーバーヘッドでバイナリ ヒープを生成できるというのは少し信じられないことなので、ここでは証明しません。ただし、ヒープが O(n) オーバーヘッドで生成されることを理解するための鍵は、logn 係数がツリーの高さに基づいているためです。 buildHeap の多くの操作では、ツリーの高さは logn よりも小さくなります。

以上がPython のバイナリ ヒープの詳細な紹介 (コード例)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。