Python排序算法之堆排序算法

更新時間：2023年01月07日 11:05:08 作者：一枚大果殼

堆排序看字面意思是一種排序方法，那堆是什么呢？堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)。其實堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。

1. 樹

樹是最基本的數(shù)據(jù)結(jié)構(gòu)，可以用樹映射現(xiàn)實世界中一對多的群體關(guān)系。如公司的組織結(jié)構(gòu)、網(wǎng)頁中標(biāo)簽之間的關(guān)系、操作系統(tǒng)中文件與目錄結(jié)構(gòu)……都可以用樹結(jié)構(gòu)描述。

樹是由結(jié)點以及結(jié)點之間的關(guān)系所構(gòu)成的集合。關(guān)于樹結(jié)構(gòu)的更多概念不是本文的主要內(nèi)容，本文只關(guān)心樹數(shù)據(jù)結(jié)構(gòu)中的幾個特殊變種：

二叉樹

如果樹中的任意結(jié)點（除葉子結(jié)點外）最多只有兩個子結(jié)點，這樣的樹稱為二叉樹。

滿二叉樹

如果 二叉樹中任意結(jié)點（除葉子結(jié)點外）都有 2 個子結(jié)點，則稱為滿二叉樹。

滿二叉樹的特性：

根據(jù)滿二叉樹的定義可知，滿二叉樹從上向下，每一層上的結(jié)點數(shù)以 2 倍的增量遞增。也可以說，滿二叉樹是一個首項為 1 ，公比為 2 的等比數(shù)列。所以：

一個層數(shù)為 k 的滿二叉樹總結(jié)點數(shù)為：2k-1 。

滿二叉樹的總結(jié)點數(shù)一定是奇數(shù)！

根據(jù)等比公式可知第 i 層上的結(jié)點數(shù)為：2i-1，因此，一個層數(shù)為 k 的滿二叉樹的葉子結(jié)點個數(shù)為: 2k-1。

什么是完全二叉樹？

完全二叉樹是滿二叉樹的一個特例。

通俗理解：在滿二叉樹基礎(chǔ)上，從右向左刪除幾個葉子節(jié)點后，此時滿二叉樹就變成了完全二叉樹。如下圖，在上圖滿二叉樹基礎(chǔ)上從右向左刪除 2 個葉結(jié)點后的結(jié)構(gòu)就是完全二叉樹。

完全二叉樹的專業(yè)概念：

一棵深度為 k 的有 n 個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進(jìn)行編號，如果編號為 i（1<=i<=n） 的結(jié)點與滿二叉樹中編號為 i 的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

專業(yè)概念有點像繞口令。

顯然，完全二叉樹的葉子結(jié)點只能出現(xiàn)在最下層或次下層，且最下層的葉子結(jié)點集中在樹的左部。

注意：滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。

2. 二叉堆

二叉堆是有序的 完全二叉樹，在完全二叉樹的基礎(chǔ)上，二叉堆 提供了有序性特征：

二叉堆 的根結(jié)點上的值是整個堆中的最小值或最大值。

當(dāng)根結(jié)點上的值是整個堆結(jié)構(gòu)中的最小值時，此堆稱為最小堆。

如果根結(jié)點上的值是整個堆結(jié)構(gòu)中的最大值時，則稱堆為最大堆。

最小堆中，任意節(jié)點的值大于父結(jié)點的值，反之，最大堆中，任意節(jié)點的值小于父結(jié)點的值。

綜合所述，二叉堆的父結(jié)點與子結(jié)點之間滿足下面的關(guān)系：

如果知道了一個結(jié)點的位置 i，則其左子結(jié)點在 2*i 處，右子結(jié)點在 2*i+1 處。

前提是結(jié)點要有子結(jié)點。

如果知道了一個結(jié)點的位置 i，則其父結(jié)點在 i除 2 處。

根結(jié)點沒有父結(jié)點。

如上圖所示：

值為 5 的結(jié)點在 2 處，則其左結(jié)點 12 的位置應(yīng)該在 2*2=4 處，而實際情況也是在 4 位置。其右子結(jié)點 13 的位置應(yīng)該在 2*2+1=5 的位置，實際位置也是在 5 位置。

值為 19 的結(jié)點現(xiàn)在 7 位置，其父結(jié)點的根據(jù)公式 7 除 2 等于 3(取整)，應(yīng)該在 3 處，而實際情況也是在 3 處（位置在 3、值為 8 的結(jié)點是其父結(jié)點）。

2.1 二叉堆的抽象數(shù)據(jù)結(jié)構(gòu)

當(dāng)談?wù)撃撤N數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)結(jié)構(gòu)時，最基本的 API 無非就是增、刪、改、查。

二叉堆的基本抽象數(shù)據(jù)結(jié)構(gòu)：

Heap() ：創(chuàng)建一個新堆。 insert(data)：向堆中添加新節(jié)點（數(shù)據(jù)）。 get_root()：返回最小（大）堆的最?。ù螅┰?。 remove_root() ：刪除根節(jié)點。 is_empty()：判斷堆是否為空。 find_all()：查詢堆中所有數(shù)據(jù)。

二叉堆雖然是樹結(jié)構(gòu)的變種，有樹的層次結(jié)構(gòu)，但因結(jié)點與結(jié)點之間有很良好的數(shù)學(xué)關(guān)系，使用 Python 中的列表存儲是非常不錯的選擇。

現(xiàn)如有一個數(shù)列=[8,5,12,15,19,13,1]，現(xiàn)使用二叉堆方式保存。先構(gòu)造一個列表。

列表中的第 0 位置初始為 0，從第 2 個位置也就是索引號為 1 的地方開始存儲堆的數(shù)據(jù)。如下圖，二叉堆中的數(shù)據(jù)在列表中的存儲位置。

2.2 API 實現(xiàn)

設(shè)計一個 Heap 類封裝對二叉堆的操作方法，類中方法用來實現(xiàn)最小堆。

'''
模擬最小堆
'''

class Heap():

    # 初始化方法
    def __init__(self):
        # 數(shù)列，第一個位置空著
        self.heap_list = [0]
        # 大小
        self.size = 0

    # 返回根結(jié)點的值
    def get_root(self):
		pass

    '''
    刪除根結(jié)點
    '''
    def remove_root(self):
        pass

    # 為根結(jié)點賦值
    def set_root(self, data):
     	pass

    # 添加新結(jié)點
    def insert(self, data):
        pass

    # 是否為空
    def is_empty(self):
        pass

Heap 類中的屬性詳解：

heap_list：使用列表存儲二叉堆的數(shù)據(jù)，初始時，列表的第 0 位置初始為默認(rèn)值 0。

為什么要設(shè)置列表的第 0 位置的默認(rèn)值為 0？

這個 0 也不是隨意指定的，有其特殊數(shù)據(jù)含義：用來描述根結(jié)點的父結(jié)點或者說根結(jié)點沒有父結(jié)點。

size：用來存儲二叉堆中數(shù)據(jù)的實際個數(shù)。

Heap 類中的方法介紹：

is_empty：檢查是不是空堆。

    # 長度為 0 ,則為空堆
    def is_empty(self):
        return self.size==0

set_root：創(chuàng)建根結(jié)點。保證根節(jié)點始終存儲在列表索引為 1 的位置。

    # 為根結(jié)點賦值
    def set_root(self, data):
        self.heap_list.insert(1, data)
        self.size += 1

get_root：如果是最大堆，則返回二叉堆的最大值，如果是最小堆，則返回二叉堆的最小值。

    # 返回根結(jié)點的值
    def get_root(self):
        # 檢查列表是否為空
        if not self.is_empty():
            return self.heap_list[1]
        raise Exception("空二叉堆！")

使用列表保存二叉堆數(shù)據(jù)時，根結(jié)點始終保存在索引號為 1 的位置。

前面是幾個基本方法，現(xiàn)在實現(xiàn)添加新結(jié)點，編碼之前，先要知道如何在二叉堆中添加新結(jié)點：

添加新結(jié)點采用上沉算法。如下演示流程描述了上沉的實現(xiàn)過程。

把新結(jié)點添加到已有的二叉堆的最后面。如下圖，添加值為 4 的新結(jié)點，存儲至索引號為 7 的位置。

查找新結(jié)點的父結(jié)點，并與父結(jié)點的值比較大小，如果比父結(jié)點的值小，則和父結(jié)點交換位置。如下圖，值為 4 的結(jié)點小于值為 8 的父結(jié)點，兩者交換位置。

交換后再查詢是否存在父結(jié)點，如果有，同樣比較大小、交換，直到到達(dá)根結(jié)點或比父結(jié)點大為止。值為 4 的結(jié)點小于值為 5 的父結(jié)點，繼續(xù)交換。交換后，新結(jié)點已經(jīng)達(dá)到了根結(jié)點位置，整個添加過程可結(jié)束。觀察后會發(fā)現(xiàn)，遵循此流程添加后，沒有破壞二叉堆的有序性。

insert 方法的實現(xiàn)：

    # 添加新節(jié)點
    def insert(self, data):
        # 添加新節(jié)點至列表最后
        self.heap_list.append(data)
        self.size += 1
        # 新節(jié)點當(dāng)前位置
        n_idx = len(self.heap_list) - 1
        while True:
            if n_idx // 2 == 0:
                # 當(dāng)前節(jié)點是根節(jié)點，根結(jié)點沒有父結(jié)點，或說父結(jié)點為 0，這也是為什么初始化列表時設(shè)置 0 為默認(rèn)值的原因
                break
            # 和父節(jié)點比較大小
            if self.heap_list[n_idx] < self.heap_list[n_idx // 2]:
                # 和父節(jié)點交換位置
                self.heap_list[n_idx], self.heap_list[n_idx // 2] = self.heap_list[n_idx // 2], self.heap_list[n_idx]
            else:
                # 出口之二
                break
            # 修改新節(jié)點的當(dāng)前位置
            n_idx = n_idx // 2

測試向二叉堆中添加數(shù)據(jù)。

創(chuàng)建一個空堆。

heap = Heap()

創(chuàng)建值為 5 的根結(jié)點。

heap.set_root(5)

檢查根結(jié)點是否創(chuàng)建成功。

val = heap.get_root()
print(val)
'''
輸出結(jié)果
5
'''

添加值為 12和值為13 的 2 個新結(jié)點，檢查添加新結(jié)點后整個二叉堆的有序性是否正確。

# 添加新結(jié)點
heap.insert(12)
heap.insert(13)
# 輸入數(shù)列
print(heap.heap_list)
'''
輸出結(jié)果
[0, 5, 12，13]
'''

添加值為 1 的新結(jié)點，并檢查二叉堆的有序性。

# 添加新結(jié)點
heap.insert(1)
print(heap.heap_list)
'''
輸出結(jié)果
[0, 1, 5, 13, 12]
'''

繼續(xù)添加值為 15、19、8 的 3 個新結(jié)點，并檢查二叉堆的狀況。

heap.insert(15)
heap.insert(19)
heap.insert(8)
print(heap.heap_list)
'''
輸出結(jié)果
[0, 1, 5, 8, 12, 15, 19, 13]
'''

介紹完添加方法后，再來了解一下，如何刪除二叉堆中的結(jié)點。

二叉堆的刪除操作從根結(jié)點開始，如下圖刪除根結(jié)點后，空出來的根結(jié)點位置，需要在整個二叉堆中重新找一個結(jié)點充當(dāng)新的根結(jié)點。

二叉堆中使用下沉算法選擇新的根結(jié)點：

找到二叉堆中的最后一個結(jié)點，移到到根結(jié)點位置。如下圖，把二叉堆中最后那個值為 19 的結(jié)點移到根結(jié)點位置。

最小堆中，如果新的根結(jié)點的值比左或右子結(jié)點的值大，則和子結(jié)點交換位置。如下圖，在二叉堆中把 19 和 5 的位置進(jìn)行交換。

注意：總是和最小的子結(jié)點交換。

交換后，如果還是不滿足最小二叉堆父結(jié)點小于子結(jié)點的規(guī)則，則繼續(xù)比較、交換新根結(jié)點直到下沉到二叉堆有序為止。如下，繼續(xù)交換 12 和 19 的值。如此反復(fù)經(jīng)過多次交換直到整個堆結(jié)構(gòu)符合二叉堆的特性。

remove_root 方法的具體實現(xiàn)：

	'''
    刪除根節(jié)點
    '''
    def remove_root(self):
        r_val = self.get_root()
        self.size -= 1
        if self.size == 1:
            # 如果只有根節(jié)點，直接刪除
            return self.heap_list.pop()
        i = 1
        # 二叉堆的最后結(jié)點成為新的根結(jié)點
        self.heap_list[i] = self.heap_list.pop()
        # 查找是否存在比自己小的子結(jié)點
        while True:
            # 子結(jié)點的位置
            min_pos = self.min_child(i)
            if min_pos is None:
                # 出口：沒有子結(jié)點或沒有比自己小的結(jié)點
                break
            # 交換
            self.heap_list[i], self.heap_list[min_pos] = self.heap_list[min_pos], self.heap_list[i]
            i = min_pos
        return r_val

    '''
    查找是否存在比自己小的子節(jié)點
    '''
    def min_child(self, i):
        # 是否有子節(jié)點
        child_pos = self.is_exist_child(i)
        if child_pos is None:
            # 沒有子結(jié)點
            return None
        if len(child_pos) == 1 and self.heap_list[i] > self.heap_list[child_pos[0]]:
            # 有 1 個子節(jié)點，且大于此子結(jié)點
            return child_pos[0]
        elif len(child_pos) == 2:
            # 有 2 個子節(jié)點，找到 2 個結(jié)點中小的那個結(jié)點
            if self.heap_list[child_pos[0]] < self.heap_list[child_pos[1]]:
                if self.heap_list[i] > self.heap_list[child_pos[0]]:
                    return child_pos[0]
            else:
                if self.heap_list[i] > self.heap_list[child_pos[1]]:
                    return child_pos[1]

    '''
    檢查是否存在子節(jié)點
    返回具體位置
    '''
    def is_exist_child(self, p_idx):
        # 左子節(jié)點位置
        l_idx = p_idx * 2
        # 右子節(jié)點位置
        r_idx = p_idx * 2 + 1
        if l_idx <= self.size and r_idx <= self.size:
            # 存在左、右子節(jié)點
            return l_idx, r_idx
        elif l_idx <= self.size:
            # 存在左子節(jié)點
            return l_idx,
        elif r_idx <= self.size:
            # 存在右子節(jié)點
        return r_idx,

remove_root 方法依賴 min_child和is_exist_child 方法：

min_child 方法用查找比父結(jié)點小的結(jié)點。

is_exist_child 方法用來查找是否存在子結(jié)點。

測試在二叉堆中刪除結(jié)點：

heap = Heap()
heap.set_root(5)
val = heap.get_root()
print(val)

# 添加新結(jié)點
heap.insert(12)
heap.insert(13)
# 添加新結(jié)點
heap.insert(1)
heap.insert(15)
heap.insert(19)
heap.insert(8)
# 添加結(jié)點后二叉堆現(xiàn)狀
print("添加結(jié)點后二叉堆現(xiàn)狀：", heap.heap_list)
val = heap.remove_root()
print("刪除根結(jié)點后二叉堆現(xiàn)狀：", heap.heap_list)
'''
輸出結(jié)果
添加節(jié)點后二叉堆現(xiàn)狀： [0, 1, 5, 8, 12, 15, 19, 13]
刪除根節(jié)點后二叉堆現(xiàn)狀： [0, 5, 12, 8, 13, 15, 19]
'''

可以看到最后二叉堆的結(jié)構(gòu)和有序性都得到了完整的保持。

3. 堆排序

堆排序指借助堆的有序性對數(shù)據(jù)進(jìn)行排序。

需要排序的數(shù)據(jù)以堆的方式保存然后再從堆中以根結(jié)點方式取出來，無序數(shù)據(jù)就會變成有序數(shù)據(jù) 。

如有數(shù)列=[4,1,8,12,5,10,7,21,3]，現(xiàn)通過堆的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序。

heap = Heap()
nums = [4,1,8,12,5,10,7,21,3]
# 創(chuàng)建根節(jié)點
heap.set_root(nums[0])
# 其它數(shù)據(jù)添加到二叉堆中
for i in range(1, len(nums)):
    heap.insert(nums[i])
print("堆中數(shù)據(jù)：", heap.heap_list)
# 獲取堆中的數(shù)據(jù)
nums.clear()
while heap.size > 0:
    nums.append(heap.remove_root())
print("排序后數(shù)據(jù)：", nums)
'''
輸出結(jié)果
堆中數(shù)據(jù)： [0, 1, 3, 7, 4, 5, 10, 8, 21, 12]
排序后數(shù)據(jù)： [1, 3, 4, 5, 7, 8, 10, 12, 21]
'''

本例中的代碼還有優(yōu)化空間，本文試圖講清楚堆的使用，優(yōu)化的地方交給有興趣者。