資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中的堆排序是什麼？
堆排序是一種基於二叉堆資料結構的排序技術。為了進行堆排序，您需要熟悉二叉樹和二叉堆。
什麼是完全二叉樹？
完全二叉樹是一種樹形資料結構，其中除了最後一層外，所有層都完全填充。最後一層必須從左側填充。
什麼是二叉堆？
二叉堆是二叉樹的一種特殊情況。二叉堆有兩種型別：
最大堆 - 每層上的父節點都大於其子節點。
最小堆 - 每層上的父節點都小於其子節點。
完全二叉樹的陣列表示
由於二叉堆的空間效率高，因此可以表示為陣列。如果父節點儲存在索引 I 處，則左子節點可以透過 2 * i + 1 計算，右子節點可以透過 2 *i + 2 計算。假設索引從 0 開始。
堆排序演算法
從完全二叉樹構建最大堆。
刪除根節點並將其替換為堆中的最後一個元素，將堆的大小減少 1，然後再次從剩餘節點構建最大堆。
重複步驟 2，直到只剩下 1 個節點。
從完全二叉樹構建最大堆
這是從完全二叉樹構建最大堆的程式碼，其中兩個子節點與根節點進行比較。如果較大的元素不是根節點，則將較大的元素與根節點交換。這是一個遞迴過程。當前小於其子節點的根節點會持續與其較低的子樹進行比較，直到到達其正確的位置。
以下程式碼從完全二叉樹構建最大堆，該二叉樹基本上是我們想要排序的陣列。
def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
堆排序
此時，我們擁有了最大堆。現在我們需要執行以下操作。
將根節點與堆中的最後一個元素交換。
將堆的大小減少 1。（這意味著最大元素已到達最後一個位置，我們不需要考慮該元素）。
重建最大堆，不包括最後一個元素。
重複上述步驟，直到只剩下 1 個元素。
for i in range(n-1, 0, -1): # Swap arr[i], arr[0] = arr[0], arr[i] # Heapify root element heapify(arr, i, 0)
Python 中堆排序的完整程式如下：
def heapify(arr, n, i):
# Find largest among root and children
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# If root is not largest, swap with largest and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
# Swap
arr[i], arr[0] = arr[0], arr[i]
# Heapify root element
heapify(arr, i, 0)
arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
print(arr[i], end=' ')時間複雜度 - O(n logn)
更新於： 2021年6月11日
362 次檢視
廣告