Python排序算法之堆排序算法
本文從樹數(shù)據(jù)結構說到二叉堆數(shù)據(jù)結構，再使用二叉堆的有序性對無序數(shù)列排序。
1. 樹
樹是最基本的數(shù)據(jù)結構，可以用樹映射現(xiàn)實世界中一對多的群體關系。如公司的組織結構、網(wǎng)頁中標簽之間的關系、操作系統(tǒng)中文件與目錄結構……都可以用樹結構描述。
樹是由結點以及結點之間的關系所構成的集合。關于樹結構的更多概念不是本文的主要內容，本文只關心樹數(shù)據(jù)結構中的幾個特殊變種：
二叉樹
如果樹中的任意結點（除葉子結點外）最多只有兩個子結點，這樣的樹稱為二叉樹。
滿二叉樹
如果 二叉樹中任意結點（除葉子結點外）都有 2 個子結點，則稱為滿二叉樹。 
滿二叉樹的特性：
根據(jù)滿二叉樹的定義可知，滿二叉樹從上向下，每一層上的結點數(shù)以 2 倍的增量遞增。也可以說，滿二叉樹是一個首項為 1 ，公比為 2 的等比數(shù)列。所以：
一個層數(shù)為 k 的滿二叉樹總結點數(shù)為：2<sup>k</sup>-1 。
滿二叉樹的總結點數(shù)一定是奇數(shù)！
根據(jù)等比公式可知第 i 層上的結點數(shù)為：2<sup>i-1</sup>，因此，一個層數(shù)為 k 的滿二叉樹的葉子結點個數(shù)為: 2<sup>k-1</sup>。
什么是完全二叉樹？
完全二叉樹是滿二叉樹的一個特例。
通俗理解： 在滿二叉樹基礎上，從右向左刪除幾個葉子節(jié)點后，此時滿二叉樹就變成了完全二叉樹。如下圖，在上圖滿二叉樹基礎上從右向左刪除 2 個葉結點后的結構就是完全二叉樹。
完全二叉樹的專業(yè)概念：
一棵深度為 k 的有 n 個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為 i（1<=i<=n） 的結點與滿二叉樹中編號為 i 的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。
專業(yè)概念有點像繞口令。
顯然，完全二叉樹的葉子結點只能出現(xiàn)在最下層或次下層，且最下層的葉子結點集中在樹的左部。
注意：滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。
2. 二叉堆
二叉堆是有序的 完全二叉樹，在完全二叉樹的基礎上，二叉堆 提供了有序性特征：
二叉堆 的根結點上的值是整個堆中的最小值或最大值。
當根結點上的值是整個堆結構中的最小值時，此堆稱為最小堆。
如果根結點上的值是整個堆結構中的最大值時，則稱堆為最大堆。
最小堆中，任意節(jié)點的值大于父結點的值，反之，最大堆中，任意節(jié)點的值小于父結點的值。
綜合所述，二叉堆的父結點與子結點之間滿足下面的關系：
如果知道了一個結點的位置 i，則其左子結點在 2*i 處，右子結點在 2*i+1 處。
前提是結點要有子結點。
如果知道了一個結點的位置 i，則其父結點在 i除 2 處。
根結點沒有父結點。
如上圖所示：
值為 5 的結點在 2 處，則其左結點 12 的位置應該在 2*2=4 處，而實際情況也是在 4 位置。其右子結點 13 的位置應該在 2*2+1=5 的位置，實際位置也是在 5 位置。
值為 19 的結點現(xiàn)在 7 位置，其父結點的根據(jù)公式 7 除 2 等于 3(取整)，應該在 3 處，而實際情況也是在 3 處（位置在 3、 值為 8 的結點是其父結點）。
2.1 二叉堆的抽象數(shù)據(jù)結構
當談論某種數(shù)據(jù)結構的抽象數(shù)據(jù)結構時，最基本的 API 無非就是增、刪、改、查。
二叉堆的基本抽象數(shù)據(jù)結構：
Heap() ：創(chuàng)建一個新堆。 insert(data)： 向堆中添加新節(jié)點（數(shù)據(jù)）。 get_root()： 返回最?。ù螅┒训淖钚。ù螅┰?。 remove_root() ：刪除根節(jié)點。 is_empty()：判斷堆是否為空。 find_all()：查詢堆中所有數(shù)據(jù)。
二叉堆雖然是樹結構的變種，有樹的層次結構，但因結點與結點之間有很良好的數(shù)學關系，使用 Python 中的列表存儲是非常不錯的選擇。
現(xiàn)如有一個數(shù)列=[8,5,12,15,19,13,1]，現(xiàn)使用二叉堆方式保存。先構造一個列表。
列表中的第 0 位置初始為 0，從第 2 個位置也就是索引號為 1 的地方開始存儲堆的數(shù)據(jù)。如下圖，二叉堆中的數(shù)據(jù)在列表中的存儲位置。
2.2 API 實現(xiàn)
設計一個 Heap 類封裝對二叉堆的操作方法，類中方法用來實現(xiàn)最小堆。
'''
模擬最小堆
'''
class Heap():
# 初始化方法
def __init__(self):
# 數(shù)列，第一個位置空著
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):
passHeap 類中的屬性詳解：
heap_list：使用列表存儲二叉堆的數(shù)據(jù)，初始時，列表的第 0 位置初始為默認值 0。
為什么要設置列表的第 0 位置的默認值為 0？
這個 0 也不是隨意指定的，有其特殊數(shù)據(jù)含義：用來描述根結點的父結點或者說根結點沒有父結點。
size：用來存儲二叉堆中數(shù)據(jù)的實際個數(shù)。
Heap 類中的方法介紹：
is_empty：檢查是不是空堆。
# 長度為 0 ,則為空堆
def is_empty(self):
return self.size==0set_root：創(chuàng)建根結點。保證根節(jié)點始終存儲在列表索引為 1 的位置。
# 為根結點賦值
def set_root(self, data):
self.heap_list.insert(1, data)
self.size += 1get_root：如果是最大堆，則返回二叉堆的最大值，如果是最小堆，則返回二叉堆的最小值。
# 返回根結點的值
def get_root(self):
# 檢查列表是否為空
if not self.is_empty():
return self.heap_list[1]
raise Exception("空二叉堆！")使用列表保存二叉堆數(shù)據(jù)時，根結點始終保存在索引號為 1 的位置。
前面是幾個基本方法，現(xiàn)在實現(xiàn)添加新結點，編碼之前，先要知道如何在二叉堆中添加新結點：
添加新結點采用上沉算法。如下演示流程描述了上沉的實現(xiàn)過程。
把新結點添加到已有的二叉堆的最后面。如下圖，添加值為 4 的新結點，存儲至索引號為 7 的位置。
查找新結點的父結點，并與父結點的值比較大小，如果比父結點的值小，則和父結點交換位置。如下圖，值為 4 的結點小于值為 8 的父結點，兩者交換位置。
交換后再查詢是否存在父結點，如果有，同樣比較大小、交換，直到到達根結點或比父結點大為止。值為 4 的結點小于值為 5 的父結點，繼續(xù)交換。交換后，新結點已經(jīng)達到了根結點位置，整個添加過程可結束。觀察后會發(fā)現(xiàn)，遵循此流程添加后，沒有破壞二叉堆的有序性。
insert 方法的實現(xiàn)：
# 添加新節(jié)點
def insert(self, data):
# 添加新節(jié)點至列表最后
self.heap_list.append(data)
self.size += 1
# 新節(jié)點當前位置
n_idx = len(self.heap_list) - 1
while True:
if n_idx // 2 == 0:
# 當前節(jié)點是根節(jié)點，根結點沒有父結點，或說父結點為 0，這也是為什么初始化列表時設置 0 為默認值的原因
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é)點的當前位置
n_idx = n_idx // 2測試向二叉堆中添加數(shù)據(jù)。
創(chuàng)建一個空堆。
heap = Heap()
創(chuàng)建值為 5 的根結點。
heap.set_root(5)
檢查根結點是否創(chuàng)建成功。
val = heap.get_root() print(val) ''' 輸出結果 5 '''
添加值為 12和值為13 的 2 個新結點，檢查添加新結點后整個二叉堆的有序性是否正確。
# 添加新結點 heap.insert(12) heap.insert(13) # 輸入數(shù)列 print(heap.heap_list) ''' 輸出結果 [0, 5, 12，13] '''
添加值為 1 的新結點，并檢查二叉堆的有序性。
# 添加新結點 heap.insert(1) print(heap.heap_list) ''' 輸出結果 [0, 1, 5, 13, 12] '''
繼續(xù)添加值為 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 的位置進行交換。
注意：總是和最小的子結點交換。
交換后，如果還是不滿足最小二叉堆父結點小于子結點的規(guī)則，則繼續(xù)比較、交換新根結點直到下沉到二叉堆有序為止。如下，繼續(xù)交換 12 和 19 的值。如此反復經(jīng)過多次交換直到整個堆結構符合二叉堆的特性。
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
# 二叉堆的最后結點成為新的根結點
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
'''
查找是否存在比自己小的子節(jié)點
'''
def min_child(self, i):
# 是否有子節(jié)點
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 個子節(jié)點，且大于此子結點
return child_pos[0]
elif len(child_pos) == 2:
# 有 2 個子節(jié)點，找到 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]
'''
檢查是否存在子節(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 方法用查找比父結點小的結點。
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)
# 添加結點后二叉堆現(xiàn)狀
print("添加結點后二叉堆現(xiàn)狀：", heap.heap_list)
val = heap.remove_root()
print("刪除根結點后二叉堆現(xiàn)狀：", heap.heap_list)
'''
輸出結果
添加節(jié)點后二叉堆現(xiàn)狀： [0, 1, 5, 8, 12, 15, 19, 13]
刪除根節(jié)點后二叉堆現(xiàn)狀： [0, 5, 12, 8, 13, 15, 19]
'''
可以看到最后二叉堆的結構和有序性都得到了完整的保持。
3. 堆排序
堆排序指借助堆的有序性對數(shù)據(jù)進行排序。
需要排序的數(shù)據(jù)以堆的方式保存 然后再從堆中以根結點方式取出來，無序數(shù)據(jù)就會變成有序數(shù)據(jù) 。
如有數(shù)列=[4,1,8,12,5,10,7,21,3]，現(xiàn)通過堆的數(shù)據(jù)結構進行排序。
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)
'''
輸出結果
堆中數(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)化的地方交給有興趣者。
4. 后記
在樹結構上加上一些新特性要求，樹會產(chǎn)生很多新的變種，如二叉樹，限制子結點的個數(shù)，如滿二叉樹，限制葉結點的個數(shù)，如完全二叉樹就是在滿二叉樹的“滿”字上做點文章，讓這個''滿"變成"不那么滿"。
在完全二叉樹上添加有序性，則會衍生出二叉堆數(shù)據(jù)結構。利用二叉堆的有序性，能輕松完成對數(shù)據(jù)的排序。
二叉堆中有 2 個核心方法，插入和刪除，這兩個方法也可以使用遞歸方式編寫。
以上就是Python排序算法之堆排序算法的詳細內容，更多關于Python 堆排序算法的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了基于python opencv單目相機標定的實現(xiàn)代碼，代碼簡單易懂，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-01-01
彩票是一個恒古不變的話題，現(xiàn)在的生活越來越好，大部分人開始關注福利彩票的事情，當然也有很多人都想中將是真的啦~哈哈哈，但是大家還是要適當哦！小編今天給大家做了一款簡易的彩票小游戲，讓我們看看誰能中一等獎吧？誰又是二等獎、三等獎呢2023-03-03
這篇文章主要介紹了關于Java中RabbitMQ的高級特性,MQ全稱為Message Queue，即消息隊列,"消息隊列"是在消息的傳輸過程中保存消息的容器,它是典型的：生產(chǎn)者、消費者模型,生產(chǎn)者不斷向消息隊列中生產(chǎn)消息，消費者不斷的從隊列中獲取消息,需要的朋友可以參考下2023-07-07
最近一個朋友說已經(jīng)轉用Zeplin很久了。Zeplin的設計稿展示頁面的顏色色值使用十進制的 RGB 表示的，在 Android 中的顏色表示大多情況下都需要十六進制的 RGB 表示。所以想寫個工作，當輸入十進制的RGB ，得到十六進制的色值，最好可以方便復制。下面來一起看看吧。2016-10-10
在Python中,使用base64模塊可以解碼Base64編碼的圖片數(shù)據(jù),首先需要去除Base64字符串的前綴,然后使用base64.b64decode()函數(shù)進行解碼,最后將解碼后的數(shù)據(jù)保存為圖片文件,適用于各種MIME類型的Base64編碼2024-09-09
這篇文章主要介紹了Python實現(xiàn)i人事自動打卡的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-01-01
這篇文章主要為大家詳細介紹了Python協(xié)程的用法和例子，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-09-09
正則表達式是對字符串操作的一種邏輯公式，就是用事先定義好的一些特定字符、及這些特定字符的組合，組成一個“規(guī)則字符串”，這個“規(guī)則字符串”用來表達對字符串的一種過濾邏輯2018-07-07
本教程并未涵蓋Python語言的全部內容，只是一個入門的教程，Python有非常多的庫以及很多的功能特點需要學習，小編只是拋磚引玉，希望大家可以從中受益2018-09-09
本代碼介紹了python算法學習中的基數(shù)排序實例，大家參考使用吧2013-12-12