python中二元堆的詳細介紹（程式碼範例）

這篇文章帶給大家的內容是關於python中二元堆的詳細介紹（程式碼範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

一、堆

資料結構 堆（heap） 是一種優先隊列。隊列是一種先進先出的資料結構。隊列的一個重要變種稱為優先權隊列。使用優先隊列能夠以任意順序增加對象，並且能在任意的時間（可能在增加對象的同時）找到（也可能移除）最小的元素，也就是說它比python的min方法更有效率。
在優先權佇列中，佇列中的項目的邏輯順序由它們的優先權決定。最高優先權項在佇列的前面，最低優先權的項在後面。因此，當你將項目排入優先權佇列時，新項目可能會一直移動到前面。

二、二元堆運算

我們的二元堆實作的基本運算如下：

BinaryHeap() 建立一個新的，空的二元堆。
insert(k) 在堆中新增一個新項目。
findMin()傳回具有最小鍵值的項，並將項留在堆中。
delMin() 傳回具有最小鍵值的項，從堆中刪除該項。
如果堆是空的，isEmpty() 回傳true，否則回傳 false。
size() 傳回堆中的項數。
buildHeap(list) 從鍵列表建立一個新的堆。

注意，無論我們在堆中新增項目的順序是什麼，每次都刪除最小的。

為了使我們的堆有效地工作，我們將利用二元樹的對數性質來表示我們的堆。為了確保對數性能，我們必須保持樹平衡。 平衡二元樹在根的左和右子樹中具有大致相同數量的節點，它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二元樹。在我們的堆實作中，我們透過創建一個 完整二元樹 來保持樹平衡。一個完整的二元樹是一個樹，其中 每層結點都完全填滿，在最後一層上如果不是滿的，則只缺少右邊的若干結點。 Figure 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)。因此用insert方法的總開銷是O(nlogn)。其實我們可以直接將整個列表生成堆，將總開銷控制在O(n)。 Listing 6 所示的是生成堆的操作。

能在O(n)的開銷下能生成二元堆看起來有點不可思議，這裡就不做證明了。但要理解用O(n)的開銷能產生堆的關鍵是因為logn因子是基於樹的高度。而對於buildHeap裡的許多操作，樹的高度比logn小。

以上是python中二元堆的詳細介紹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！