最小堆實現優先隊列：Python實現 - zjutzz－IT工程師數位筆記本

文章出處

堆是一種數據結構，因為Heapsort而被提出。除了堆排序，“堆”這種數據結構還可以用于優先隊列的實現。

堆首先是一個完全二叉樹：它除了最底層之外，樹的每一層的都是滿的，且最底層中的節點處于左邊，相互之間沒有“跳變”；其次，堆有次序屬性：每個節點中的數據項都大于或者等于其子女的數據項（如果是記錄，則這些記錄中的某個關鍵域必須滿足這一屬性）。當然，這是指大頂堆，小頂堆則是父節點比子節點都要小。

所謂隊列，就是一個FIFO表（first in， first out）。優先隊列，就是在隊列的基礎上，每個元素加一個優先級，last in的元素可能會first out，這就是優先級在起作用。

我想實現這樣一個優先隊列：

　　元素為整數

　　元素值小的優先級反而大

　　有入隊操作，每次進入一個元素

　　出隊操作，也行每次一個元素

那么，我的小根堆Heap應該這樣考慮：

　　每當插入元素時，在原有Heap的最后一個葉子節點后面插入新元素val，并持續比較val和其父節點的值之間是否滿足堆的次序屬性，直到滿足

　　每當刪除元素時，刪除的是值最小的元素，也就是根結點root，則將root和最后一個葉子節點lastleaf互換，然后刪除交換后的new_lastleaf ，并從new_root開始調整堆，使滿足堆的次序屬性。

這樣一來，代碼就不難寫出：

#coding:utf8
#author:HaxtraZ
#description:優先隊列，用堆實現
#修改自《算法導論》2nd Edition


class ZHeap:
    def __init__(self, item=[]):
        # 初始化。item為數組
        self.items = item
        self.heapsize = len(self.items)

    def LEFT(self, i):
        return 2 * i + 1

    def RIGHT(self, i):
        return 2 * i + 2

    def PARENT(self, i):
        return (i - 1) / 2

    def MIN_HEAPIFY(self, i):
        # 最小堆化：使以i為根的子樹成為最小堆
        l = self.LEFT(i)
        r = self.RIGHT(i)
        if l < self.heapsize and self.items[l] < self.items[i]:
            smallest = l
        else:
            smallest = i

        if r < self.heapsize and self.items[r] < self.items[smallest]:
            smallest = r

        if smallest != i:
            self.items[i], self.items[smallest] = self.items[smallest], self.items[i]
            self.MIN_HEAPIFY(smallest)

    def INSERT(self, val):
        # 插入一個值val，并且調整使滿足堆結構
        self.items.append(val)
        idx = len(self.items) - 1
        parIdx = self.PARENT(idx)
        while parIdx >= 0:
            if self.items[parIdx] > self.items[idx]:
                self.items[parIdx], self.items[idx] = self.items[idx], self.items[parIdx]
                idx = parIdx
                parIdx = self.PARENT(parIdx)
            else:
                break
        self.heapsize += 1

    def DELETE(self):
        last = len(self.items) - 1
        if last < 0:
            # 堆為空
            return None
        # else:
        self.items[0], self.items[last] = self.items[last], self.items[0]
        val = self.items.pop()
        self.heapsize -= 1
        self.MIN_HEAPIFY(0)
        return val


    def BUILD_MIN_HEAP(self):
        # 建立最小堆, O(nlog(n))
        i = self.PARENT(len(self.items) - 1)
        while i >= 0:
            self.MIN_HEAPIFY(i)
            i -= 1

    def SHOW(self):
        print self.items


class ZPriorityQ(ZHeap):
    def __init__(self, item=[]):
        ZHeap.__init__(self, item)

    def enQ(self, val):
        ZHeap.INSERT(self, val)

    def deQ(self):
        val = ZHeap.DELETE(self)
        return val


a = [1, 3, 2, 4, 8, 6, 22, 9]
pq = ZPriorityQ()
n = len(a)
for i in range(n):
    pq.enQ(a[i])
    pq.SHOW()

for i in range(n):
    pq.deQ()
    pq.SHOW()

　　其中，ZHeap表示小根堆，ZPriorityQ表示優先隊列，deQ表示退隊，enQ表示入隊。

　　我們發現以下結論：大根堆用于升序排序，小根堆用于降序排序。

　　為什么用堆來實現優先隊列？原因只有一個：復雜度低。

　　　　如果使用列表（存放在list中），插入為O（1），刪除為O(n)；

　　　　如果使用按照優先級排好序的有序列表，插入和線性插入排序一樣，O（n），刪除則為O(1)

　　使用堆的時候，無論你刪除還是插入，都是O（lg n）時間復雜度，對于插入和刪除都比較頻繁的操作來講，這是最好不過的了。

　　如果認為有不正確的地方歡迎拍磚。

文章列表