一、python沒有大頂堆的原因
Python沒有內置大頂堆,是因為在實際使用中,大頂堆并不是那么常用。相比之下,小頂堆和普通的堆操作更具有廣泛的應用場景,例如在排序算法、圖論算法、貪心算法、動態規劃等各種算法中都可以看到堆的身影。
此外,Python的設計哲學也與內置大頂堆不太相關。Python的優勢在于其簡單、易學、易用、可讀性好等特點,而內置大頂堆對于一個通用的高級編程語言來說,顯得過于專用和冗余。因此,Python通過標準庫模塊heapq提供了一組堆操作函數,使用者可以方便地根據需要構建小頂堆或者大頂堆,同時也避免了引入過多的不必要的數據類型和接口。
二、構造大頂堆的方法
堆是一種特殊的完全二叉樹,使用數組存儲二叉樹時,若某個非葉子節點存儲在下標為i的位置,其左右孩子節點分別存儲在下標為2i+1和2i+2的位置。堆可以分為大頂堆和小頂堆,對大頂堆來說,任意非葉子節點不小于其左右孩子節點,對于小頂堆來說,任意非葉子節點不大于其左右孩子節點。若使用數組存儲大頂堆,則滿足:arr[i] >= arr[2i+1] && arr[i] >=arr[2i+2](i為非葉子節點的在數組中的下標)
基本思想:
從最后一個非葉子節點開始,逐一比較非葉子節點和其左右孩子節點根據比較結果交換節點因為交換可能導致孩子節點不再滿足大頂堆的性質,所以需要對孩子節點進行調整。三、python實現大頂堆的方法
python中雖然沒有內置大頂堆數據結構,但可以通過其他方法實現大頂堆。實現步驟如下:
1、創建MaxHeap類
初始化,存儲最大元素數量、元素值計算函數、元素列表,當前元素數量。
class MaxHeap(object): def __init__(self, max_size, fn): self.max_size = max_size self.fn = fn self.items = [None] * max_size self.size = 0
2、獲取大頂堆各個屬性
def __str__(self): item_values = str([self.fn(self.items[i]) for i in range(self.size)]) return "Size: %d\nMax size: %d\nItem_values: %s\n" % (self.size, self.max_size, item_values)
3、檢查大頂堆是否已滿
@propertydef full(self): return self.size == self.max_size
4、添加元素
def add(self, item): if self.full: if self.fn(item) < self.value(0): self.items[0] = item self._shift_down(0) else: self.items[self.size] = item self.size += 1 self._shift_up(self.size - 1)
5、推出頂部元素
def pop(self): assert self.size > 0, "Cannot pop item! The MaxHeap is empty!" ret = self.items[0] self.items[0] = self.items[self.size - 1] self.items[self.size - 1] = None self.size -= 1 self._shift_down(0) return ret
6、元素上浮
def _shift_up(self, idx): assert idx < self.size, "The parameter idx must be less than heap's size!" parent = (idx - 1) // 2 while parent >= 0 and self.value(parent) < self.value(idx): self.items[parent], self.items[idx] = self.items[idx], self.items[parent] idx = parent parent = (idx - 1) // 2
7、元素下沉
def _shift_down(self, idx): child = (idx + 1) * 2 - 1 while child < self.size: if child + 1 < self.size and self.value(child + 1) > self.value(child): child += 1 if self.value(idx) < self.value(child): self.items[idx], self.items[child] = self.items[child], self.items[idx] idx = child child = (idx + 1) * 2 - 1 else: break
延伸閱讀1:什么是堆數據結構
堆是一種完全二叉樹,復習一下完全二叉樹的定義,完全二叉樹的形式是指除了最后一層之外,其他所有層的結點都是滿的,而最后一層的所有結點都靠左邊。教材上定義如下:若設二叉樹的深度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第 h 層所有的結點都連續集中在最左邊,這就是完全二叉樹。