国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 為什么python沒有大頂堆?

為什么python沒有大頂堆?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 05:30:39 1696973439

一、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 層所有的結點都連續集中在最左邊,這就是完全二叉樹。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT