網站首頁編程語言正文

Python排序算法之堆排序算法_python

作者：一枚大果殼 ? 更新時間： 2023-02-17 編程語言

1. 樹

樹是最基本的數據結構，可以用樹映射現實世界中一對多的群體關系。如公司的組織結構、網頁中標簽之間的關系、操作系統中文件與目錄結構……都可以用樹結構描述。

樹是由結點以及結點之間的關系所構成的集合。關于樹結構的更多概念不是本文的主要內容，本文只關心樹數據結構中的幾個特殊變種：

二叉樹

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

滿二叉樹

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

滿二叉樹的特性：

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

一個層數為 k 的滿二叉樹總結點數為：2k-1 。

滿二叉樹的總結點數一定是奇數！

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

什么是完全二叉樹？

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

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

完全二叉樹的專業概念：

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

專業概念有點像繞口令。

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

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

2. 二叉堆

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

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

當根結點上的值是整個堆結構中的最小值時，此堆稱為最小堆。

如果根結點上的值是整個堆結構中的最大值時，則稱堆為最大堆。

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

綜合所述，二叉堆的父結點與子結點之間滿足下面的關系：

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

前提是結點要有子結點。

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

根結點沒有父結點。

如上圖所示：

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

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

2.1 二叉堆的抽象數據結構

當談論某種數據結構的抽象數據結構時，最基本的 API 無非就是增、刪、改、查。

二叉堆的基本抽象數據結構：

Heap() ：創建一個新堆。 insert(data)：向堆中添加新節點（數據）。 get_root()：返回最小（大）堆的最小（大）元素。 remove_root() ：刪除根節點。 is_empty()：判斷堆是否為空。 find_all()：查詢堆中所有數據。

二叉堆雖然是樹結構的變種，有樹的層次結構，但因結點與結點之間有很良好的數學關系，使用 Python 中的列表存儲是非常不錯的選擇。

現如有一個數列=[8,5,12,15,19,13,1]，現使用二叉堆方式保存。先構造一個列表。

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

2.2 API 實現

設計一個 Heap 類封裝對二叉堆的操作方法，類中方法用來實現最小堆。

'''
模擬最小堆
'''

class Heap():

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

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

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

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

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

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

Heap 類中的屬性詳解：

heap_list：使用列表存儲二叉堆的數據，初始時，列表的第 0 位置初始為默認值 0。

為什么要設置列表的第 0 位置的默認值為 0？

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

size：用來存儲二叉堆中數據的實際個數。

Heap 類中的方法介紹：

is_empty：檢查是不是空堆。

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

set_root：創建根結點。保證根節點始終存儲在列表索引為 1 的位置。

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

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

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

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

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

添加新結點采用上沉算法。如下演示流程描述了上沉的實現過程。

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

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

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

insert 方法的實現：

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

測試向二叉堆中添加數據。

創建一個空堆。

heap = Heap()

創建值為 5 的根結點。

heap.set_root(5)

檢查根結點是否創建成功。

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

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

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

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

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

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

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

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

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

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

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

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

注意：總是和最小的子結點交換。

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

remove_root 方法的具體實現：

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

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

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

remove_root 方法依賴 min_child和is_exist_child 方法：

min_child 方法用查找比父結點小的結點。

is_exist_child 方法用來查找是否存在子結點。

測試在二叉堆中刪除結點：

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

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

可以看到最后二叉堆的結構和有序性都得到了完整的保持。

3. 堆排序

堆排序指借助堆的有序性對數據進行排序。

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

如有數列=[4,1,8,12,5,10,7,21,3]，現通過堆的數據結構進行排序。

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

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

4. 后記

在樹結構上加上一些新特性要求，樹會產生很多新的變種，如二叉樹，限制子結點的個數，如滿二叉樹，限制葉結點的個數，如完全二叉樹就是在滿二叉樹的“滿”字上做點文章，讓這個''滿"變成"不那么滿"。

在完全二叉樹上添加有序性，則會衍生出二叉堆數據結構。利用二叉堆的有序性，能輕松完成對數據的排序。

二叉堆中有 2 個核心方法，插入和刪除，這兩個方法也可以使用遞歸方式編寫。

原文鏈接：https://blog.51cto.com/gkcode/5235394

上一篇：python語法教程之def()函數定義及用法_python
下一篇：Python?樹表查找（二叉排序樹、平衡二叉樹）_pytho

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁編程語言正文

Python排序算法之堆排序算法_python

目錄

1. 樹

滿二叉樹的特性：

什么是完全二叉樹？

完全二叉樹的專業概念：

2. 二叉堆

2.1 二叉堆的抽象數據結構

2.2 API 實現

3. 堆排序

4. 后記

相關推薦

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁 編程語言 正文

Python排序算法之堆排序算法_python

目錄

1. 樹

滿二叉樹的特性：

什么是完全二叉樹？

完全二叉樹的專業概念：

2. 二叉堆

2.1 二叉堆的抽象數據結構

2.2 API 實現

3. 堆排序

4. 后記

相關推薦

網站首頁編程語言正文