一、python沒有大頂堆的原因

Python沒有內(nèi)置大頂堆，是因?yàn)樵趯?shí)際使用中，大頂堆并不是那么常用。相比之下，小頂堆和普通的堆操作更具有廣泛的應(yīng)用場(chǎng)景，例如在排序算法、圖論算法、貪心算法、動(dòng)態(tài)規(guī)劃等各種算法中都可以看到堆的身影。

此外，Python的設(shè)計(jì)哲學(xué)也與內(nèi)置大頂堆不太相關(guān)。Python的優(yōu)勢(shì)在于其簡(jiǎn)單、易學(xué)、易用、可讀性好等特點(diǎn)，而內(nèi)置大頂堆對(duì)于一個(gè)通用的高級(jí)編程語(yǔ)言來(lái)說(shuō)，顯得過于專用和冗余。因此，Python通過標(biāo)準(zhǔn)庫(kù)模塊heapq提供了一組堆操作函數(shù)，使用者可以方便地根據(jù)需要構(gòu)建小頂堆或者大頂堆，同時(shí)也避免了引入過多的不必要的數(shù)據(jù)類型和接口。

二、構(gòu)造大頂堆的方法

堆是一種特殊的完全二叉樹，使用數(shù)組存儲(chǔ)二叉樹時(shí)，若某個(gè)非葉子節(jié)點(diǎn)存儲(chǔ)在下標(biāo)為i的位置，其左右孩子節(jié)點(diǎn)分別存儲(chǔ)在下標(biāo)為2i+1和2i+2的位置。堆可以分為大頂堆和小頂堆，對(duì)大頂堆來(lái)說(shuō)，任意非葉子節(jié)點(diǎn)不小于其左右孩子節(jié)點(diǎn)，對(duì)于小頂堆來(lái)說(shuō)，任意非葉子節(jié)點(diǎn)不大于其左右孩子節(jié)點(diǎn)。若使用數(shù)組存儲(chǔ)大頂堆，則滿足：arr[i] >= arr[2i+1] && arr[i] >=arr[2i+2]（i為非葉子節(jié)點(diǎn)的在數(shù)組中的下標(biāo)）

基本思想：

三、python實(shí)現(xiàn)大頂堆的方法

python中雖然沒有內(nèi)置大頂堆數(shù)據(jù)結(jié)構(gòu)，但可以通過其他方法實(shí)現(xiàn)大頂堆。實(shí)現(xiàn)步驟如下：

1、創(chuàng)建MaxHeap類

初始化，存儲(chǔ)最大元素?cái)?shù)量、元素值計(jì)算函數(shù)、元素列表，當(dāng)前元素?cái)?shù)量。

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、獲取大頂堆各個(gè)屬性

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：什么是堆數(shù)據(jù)結(jié)構(gòu)

堆是一種完全二叉樹，復(fù)習(xí)一下完全二叉樹的定義，完全二叉樹的形式是指除了最后一層之外，其他所有層的結(jié)點(diǎn)都是滿的，而最后一層的所有結(jié)點(diǎn)都靠左邊。教材上定義如下：若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。