在文章【資料結構Python描述】樹堆（heap）簡介和Python手工實作及使用樹堆實作優先級佇列中，為了能對優先級佇列中鍵值對的增刪都較為高效，我們基于二叉堆實作了HeapPriorityQueue，

對于使用HeapPriorityQueue創建的物件q，其中用于保存優先級佇列鍵值對的二叉堆初始為空，如后續需要通過優先級佇列操作的鍵值對數量為 n n n，雖然我們大可以重復呼叫 n n n次物件q的add(k, v)方法來構建堆，但是根據文章【常見演算法Python描述】優先級佇列應用之實作選擇排序、插入排序和堆排序的分析，該操作的最壞時間復雜度為 n l o g ( n ) nlog(n) nlog(n)，

如果 n n n對鍵值對提前給定，如【常見演算法Python描述】優先級佇列應用之實作選擇排序、插入排序和堆排序中具有 n n n個元素的待排序集合，此時就可通過本文下面將介紹的自底向上（Bottom-Up）方式構建二叉堆，這種方式的最壞時間復雜度為 O ( n ) O(n) O(n)，

一、堆資料結構創建

為描述方便，下面介紹自底向上構建堆的方式時，假設給定數量為 n = 2 h + 1 ? 1 n=2^{h+1}-1 n=2h+1?1（其中 h h h為堆的高度）的任意順序鍵值對，則數量為 n n n的鍵值對恰好可以填滿高度為 h h h的完全二叉樹，且每一層的鍵值對數量分別為 1 1 1、 2 1 2^1 21、 2 2 2^2 22、 ? ? ? \cdot\cdot\cdot ???、 2 h ? 1 2^{h-1} 2h?1、 2 h {2^h} 2h，此時二叉樹的高度為 h = l o g ( n + 1 ) ? 1 h=log(n+1)-1 h=log(n+1)?1，

1. 建堆步驟

下面以給定 n = 15 n=15 n=15個鍵值對為例介紹如何自底向上構建堆：

易知，上述 n = 15 n=15 n=15個鍵值對可以填滿高度為 h = l o g ( 16 ) ? 1 = 3 h=log(16)-1=3 h=log(16)?1=3的完全二叉樹（但根據堆的定義，此時完全二叉樹還不是堆），如下圖(a)所示：

下面的圖(b)至圖(h)介紹了具體的建堆程序：

• 第一步（如圖(b)所示），構建 ( 15 + 1 ) / 2 1 = 8 (15+1)/{2^1}=8 (15+1)/21=8個僅有一個鍵值對的堆：

• 第二步：
  • 首先如圖(c)所示，構建 ( 15 + 1 ) / 2 2 = 4 (15+1)/{2^2}=4 (15+1)/22=4個完全二叉樹，每個包含 3 3 3個鍵值對；
  • 然后如圖(d)所示，因為每個完全二叉樹都可能違背堆序性質，因此可能需要進行父子結點間鍵值對的交換，最后才能得到 4 4 4個堆，

• 第三步：
  • 首先如圖(e)所示，構建 ( 15 + 1 ) / 2 3 = 2 (15+1)/{2^3}=2 (15+1)/23=2個完全二叉樹，每個包含 7 7 7個鍵值對；
  • 然后如圖(f)所示，因為每個完全二叉樹都可能違背堆序性質，因此可能需要進行父子結點間鍵值對的交換，最后才能得到 2 2 2個堆，

• 第四步：
  • 首先如圖(g)所示，構建 ( 15 + 1 ) / 2 4 = 1 (15+1)/{2^4}=1 (15+1)/24=1個完全二叉樹，其中包含 15 15 15個鍵值對；
  • 然后如圖(h)所示，因為該完全二叉樹都可能違背堆序性質，因此可能需要進行父子結點間鍵值對的交換，最后才能得到根據給定的 15 15 15個鍵值對需構建的 1 1 1個二叉堆，

2. 建堆實作

分析上述建堆程序可知，實作建堆最重要的是如何將兩個形態和大小完全相同的子堆在根結點處進行合并，且保證合并后得到的完全二叉樹是一個二叉堆，

實際上，對于以串列方式給出鍵值對形式結點元素的完全二叉樹，文章【資料結構Python描述】樹堆（heap）簡介和Python手工實作及使用樹堆實作優先級佇列中介紹的自堆頂向下冒泡演算法實作_downheap()恰好可以滿足該需求，

具體地，在實作上述建堆程序時，只需要對完全二叉樹從最底層最右側結點開始直到根結點的每一個結點使用一個回圈，依次呼叫_downheap()方法即可，

更進一步地，因為_downheap()方法不對葉子結點執行任何操作，所以上述回圈只需從最底層的非葉子結點開始依次呼叫_downheap()方法，

對上述分析使用Python實作如下：

def __init__(self, contents=tuple()):
    """
    初始化一個優先級佇列
    默認將新創建的優先級佇列初始化為空，如果提前給定元素為(k, v)形式的contents集合，則使用contents初始化優先級佇列
    :param contents:(k, v)形式元素contents集合
    """
    self._data = [self._Item(k, v) for k, v in contents]
    if len(self._data) > 1:
        self._heapify()

def _heapify(self):
    """
    具體執行自底向上建堆
    :return: None
    """
    start = self._parent(len(self) - 1)  # 從最后一個葉子結點的父結點開始
    for j in range(start, -1, -1):  # 自底向上
        self._downheap(j)

分析上述代碼可知，建堆實作只是將HeapPriorityQueue的__init__()方法進行了重新設計并提供了一個非公有的實用方法_heapify()，其邏輯為：在使用HeapPriorityQueue創建物件時，其初始化方法接收一個可選引數contents，該引數是元素為(k, v)形式的元組，與舊的初始化方法不同的是，這里使用串列推導式初始化后續建堆用的串列，

3. 建堆效率

為了分析自底向上建堆的實作_heapify()方法的時間復雜度，這里：

• 首先給出結論：

針對提前給定的 n n n個鍵值對，如采用自底向上的方式構建堆，則假定鍵值對間兩兩比較的時間復雜度為 O ( 1 ) O(1) O(1)，則該建堆方式的最壞時間復雜度為 O ( n ) O(n) O(n)，

• 然后以上述給定的 15 15 15個鍵值對為例進行驗證；
• 最后再進行一般性分析，

對于給定具有任意順序的 15 15 15個鍵值對：

在_heapify()中，最壞情況下，回圈每一次迭代的運行時間正比于當前結點到最底層結點（此處為第 4 4 4層結點）的高度，因此：

• 第 4 4 4層結點數量為 2 3 = 8 2^{3}=8 23=8，但是_heapify()不對這些結點執行任何操作，因此本層的時間復雜度為 0 0 0；
• 第 3 3 3層結點數量為 2 2 = 4 2^{2}=4 22=4，當前所有結點到最底層結點（此處為第 4 4 4層結點）的高度為 1 1 1，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 4 × 1 = 4 4\times1=4 4×1=4；
• 第 2 2 2層結點數量為 2 1 = 2 2^{1}=2 21=2，當前所有結點到最底層結點（此處為第 4 4 4層結點）的高度為 2 2 2，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 2 × 2 = 4 2\times2=4 2×2=4；
• 第 1 1 1層結點數量為 2 0 = 1 2^{0}=1 20=1，當前所有結點到最底層結點（此處為第 4 4 4層結點）的高度為 3 3 3，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 1 × 3 = 3 1\times3=3 1×3=3，

綜上，即_heapify()的最壞時間復雜度正比于 4 + 4 + 3 = 11 < 15 4+4+3=11<15 4+4+3=11<15，

一般地，對于給定具有任意順序的 n = 2 h + 1 ? 1 n=2^{h+1}-1 n=2h+1?1個鍵值對：

• 第 h h h層結點數量為 2 h 2^h 2h，但是_heapify()不對這些結點執行任何操作，因此本層的時間復雜度為 0 0 0；
• 第 h ? 1 h-1 h?1層結點數量為 2 h ? 1 2^{h-1} 2h?1，當前所有結點到的高度為 1 1 1，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 2 h ? 1 × 1 {2^{h-1}}\times1 2h?1×1；
• 第 h ? 2 h-2 h?2層結點數量為 2 h ? 2 2^{h-2} 2h?2，當前所有結點到的高度為 2 2 2，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 2 h ? 2 × 2 {2^{h-2}}\times2 2h?2×2；
• ? ? ? ? ? ? \cdot\cdot\cdot\cdot\cdot\cdot ??????
• 第 h ? j h-j h?j層結點數量為 2 h ? j 2^{h-j} 2h?j，當前所有結點到的高度為 j j j，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 2 h ? j × j {2^{h-j}}\times{j} 2h?j×j；
• ? ? ? ? ? ? \cdot\cdot\cdot\cdot\cdot\cdot ??????
• 第 0 0 0層結點數量為 2 0 2^{0} 20，當前所有結點到的高度為 h h h，則對該層每個結點呼叫_downheap()的最壞時間復雜度正比于 2 0 × h {2^{0}}\times{h} 20×h，

因此，總的建堆時間復雜度正比于：

f ( n ) = ∑ j = 0 h j 2 h ? j f(n)=\sum\nolimits_{j=0}^{h}{j}{2^{h-j}} f(n)=∑j=0h?j2h?j

變形后得：

f ( n ) = 2 h ∑ j = 0 h j 2 j f(n)={2^h}\sum\nolimits_{j=0}^{h}{\frac{j}{2^j}} f(n)=2h∑j=0h?2jj?

因此，重點是求下列運算式的和：

∑ j = 0 h j 2 j \sum\nolimits_{j=0}^{h}{\frac{j}{2^j}} ∑j=0h?2jj?

為了求出上述運算式的和，需要使用下面的數學技巧：

• 首先，根據高中數學知識，對任意 x < 1 x\lt1 x<1，有下列等比數列求和公式：

∑ j = 0 ∞ x j = 1 1 ? x \sum\nolimits_{j=0}^{\infty}{x^j}=\frac{1}{1-x} ∑j=0∞?xj=1?x1?

• 然后，上述等式兩端對 x x x求導后得：

∑ j = 0 ∞ j x j ? 1 = 1 ( 1 ? x ) 2 \sum\nolimits_{j=0}^{\infty}{j}{x^{j-1}}=\frac{1}{(1-x)^2} ∑j=0∞?jxj?1=(1?x)21?

上式兩邊同乘以 x x x后得：

∑ j = 0 ∞ j x j = x ( 1 ? x ) 2 \sum\nolimits_{j=0}^{\infty}{j}{x^{j}}=\frac{x}{(1-x)^2} ∑j=0∞?jxj=(1?x)2x?

• 最后，如果令上述等式 x = 1 / 2 x={\left.1\middle/2\right.} x=1/2，則：

∑ j = 0 ∞ j 2 j = 1 / 2 ( 1 ? ( 1 / 2 ) ) 2 = 2 \sum\nolimits_{j=0}^{\infty}\frac{j}{2^j}=\frac{{\left.1\middle/2\right.}}{(1-({\left.1\middle/2\right.}))^2}=2 ∑j=0∞?2jj?=(1?(1/2))21/2?=2

因此：

f ( n ) = 2 h ∑ j = 0 h j 2 j < 2 h ∑ j = 0 ∞ j 2 j = 2 h × 2 = 2 h + 1 f(n)={2^h}\sum\nolimits_{j=0}^{h}{\frac{j}{2^j}}\lt{{2^h}\sum\nolimits_{j=0}^{\infty}{\frac{j}{2^j}}}=2^h\times{2}=2^{h+1} f(n)=2h∑j=0h?2jj?<2h∑j=0∞?2jj?=2h×2=2h+1

又本節開頭假定 n = 2 h + 1 ? 1 n=2^{h+1}-1 n=2h+1?1，于是 f ( n ) < n + 1 ∈ O ( n ) f(n)\lt{n+1}\in{O(n)} f(n)<n+1∈O(n)，至此，證畢，

二、完整測驗代碼

下面是針對【資料結構Python描述】樹堆（heap）簡介和Python手工實作及使用樹堆實作優先級佇列中實作的HeapPriorityQueue，使用自底向上建堆方法完善后得到的最終結果及其測驗代碼：

# heap_priority_queue.py
from priority_queue import PriorityQueueBase


class Empty(Exception):
    """嘗試對空優先級佇列進行洗掉操作時拋出的例外"""
    pass


class HeapPriorityQueue(PriorityQueueBase):
    """使用堆存盤鍵值對形式記錄的優先級佇列"""

    def __init__(self, contents=tuple()):
        """
        初始化一個優先級佇列
        默認將新創建的優先級佇列初始化為空，如果提前給定元素為(k, v)形式的contents集合，則使用contents初始化優先級佇列
        :param contents:(k, v)形式元素contents集合
        """
        self._data = [self._Item(k, v) for k, v in contents]
        if len(self._data) > 1:
            self._heapify()

    def _heapify(self):
        """
        具體執行自底向上建堆
        :return: None
        """
        start = self._parent(len(self) - 1)  # 從最后一個葉子結點的父結點開始
        for j in range(start, -1, -1):  # 自底向上
            self._downheap(j)

    def _parent(self, j):
        """
        回傳父結點處業務元素在串列中的索引
        :param j: 任意結點處的業務元素在串列中的索引
        :return: 父結點處業務元素在串列中的索引
        """
        return (j - 1) // 2

    def _left(self, j):
        """
        回傳左子結點處業務元素在串列中的索引
        :param j: 任意結點處的業務元素在串列中的索引
        :return: 左子結點處業務元素在串列中的索引
        """
        return 2 * j + 1

    def _right(self, j):
        """
        回傳右子結點處業務元素在串列中的索引
        :param j: 任意結點處的業務元素在串列中的索引
        :return: 右子結點處業務元素在串列中的索引
        """
        return 2 * j + 2

    def _has_left(self, j):
        """
        如結點有左子結點則回傳True，否則回傳False
        :param j: 任意結點處的業務元素在串列中的索引
        :return: 判斷結點是否有左子結點的Boolean結果
        """
        return self._left(j) < len(self._data)  # 確保串列索引不越界

    def _has_right(self, j):
        """
        如結點有右子結點則回傳True，否則回傳False
        :param j: 任意結點處的業務元素在串列中的索引
        :return: 判斷結點是否有右子結點的Boolean結果
        """
        return self._right(j) < len(self._data)  # 確保串列索引不越界

    def _swap(self, i, j):
        """
        交換一對父子結點的業務元素
        :param i: 業務元素在串列中的索引
        :param j: 業務元素在串列中的索引
        :return: None
        """
        self._data[i], self._data[j] = self._data[j], self._data[i]

    def _upheap(self, j):
        """
        自堆底向上冒泡演算法
        :param j: 結點處業務元素在串列中的索引
        :return: None
        """
        parent = self._parent(j)
        if j > 0 and self._data[j] < self._data[parent]:
            self._swap(j, parent)
            self._upheap(parent)  # 遞回呼叫

    def _downheap(self, j):
        """
        自堆頂向下冒泡演算法
        :param j: 結點處業務元素在串列中的索引
        :return: None
        """
        if self._has_left(j):
            left = self._left(j)
            small_child = left
            # 如果有左、右兩個子結點，令small_child參考鍵較小子結點的業務元素在串列中的索引
            if self._has_right(j):
                right = self._right(j)
                if self._data[right] < self._data[left]:
                    small_child = right
            # 至少根結點有左子結點時，才有可能self雖然是完全二叉樹但不是堆
            if self._data[small_child] < self._data[j]:
                self._swap(j, small_child)
                self._downheap(small_child)  # 遞回呼叫

    def __len__(self):
        """回傳優先級佇列中的記錄條目數"""
        return len(self._data)

    def __iter__(self):
        """生成優先級佇列中所有記錄的一個迭代"""
        for each in self._data:
            yield each

    def add(self, key, value):
        """向優先級佇列中插入一條key-value記錄"""
        self._data.append(self._Item(key, value))  # 新記錄條目插入并確保完全二叉樹性質
        self._upheap(len(self._data) - 1)  # 確保滿足堆序性質

    def min(self):
        """回傳（但不洗掉）優先級佇列中鍵最小的記錄，如優先級佇列此時為空則拋出例外"""
        if self.is_empty():
            raise Empty('優先級佇列為空！')
        item = self._data[0]
        return item.key, item.value

    def remove_min(self):
        """回并洗掉優先級佇列中鍵最小的記錄，如優先級佇列此時為空則拋出例外"""
        if self.is_empty():
            raise Empty('優先級佇列為空！')
        self._swap(0, len(self._data) - 1)  # 將根結點處鍵最小記錄交換至完全二叉樹最底層最右側結點處
        item = self._data.pop()
        self._downheap(0)  # 確保完全二叉樹滿足堆序性質，即確定需保存在根結點處的鍵最小記錄
        return item.key, item.value


if __name__ == '__main__':
    heap_queue = HeapPriorityQueue()
    print(heap_queue.is_empty())  # True

    heap_queue.add(4, 'C')
    heap_queue.add(6, 'Z')
    heap_queue.add(7, 'Q')
    heap_queue.add(5, 'A')
    print(heap_queue)  # [(4, 'C'), (5, 'A'), (7, 'Q'), (6, 'Z')]

    heap_queue.add(2, 'T')
    print(heap_queue)  # [(2, 'T'), (4, 'C'), (7, 'Q'), (6, 'Z'), (5, 'A')]

    print(heap_queue.remove_min())  # (2, 'T')
    print(heap_queue.remove_min())  # (4, 'C')
    print(heap_queue)  # [(5, 'A'), (6, 'Z'), (7, 'Q')]
    print(heap_queue.min())  # (5, 'A')
    print(heap_queue.is_empty())  # False

實際上，雖然我們在分析自底向上建堆方式時假設給定的價值對個數為 n = 2 h + 1 ? 1 n=2^{h+1}-1 n=2h+1?1個，但實際上對于任意數量的鍵值對，上述實作的_heapify()方法均支持，具體留待讀者思考，

三、參考資料

• [1] Lecture 14: HeapSort Analysis and Partitioning