在python中實現堆排序的步驟是：1. 構建最大堆，從最后一個非葉子節點開始調整。2. 排序時，將堆頂元素與數組末尾元素交換，縮小堆并重新調整。堆排序的時間復雜度為o(n log n)，但不是穩定排序，適合大規模數據。
def heapify(arr, n, i): largest = i; left = 2 i + 1; right = 2 i + 2if left arr[largest]: largest = leftif right arr[largest]: largest = rightif largest != i: arr[i], arr[largest] = arr[largest], arr[i]; heapify(arr, n, largest)
def heap_sort(arr): n = len(arr)for i in range(n // 2 – 1, -1, -1): heapify(arr, n, i)for i in range(n – 1, 0, -1): arr[0], arr[i] = arr[i], arr[0]; heapify(arr, i, 0)return arr
在python中實現堆排序真是一件有趣的事情，不僅能讓你深入理解算法，還能讓你看到代碼的優雅與效率。那么，如何在Python中實現堆排序呢？讓我們從頭開始，逐步構建一個高效的堆排序實現。
立即學習“Python免費學習筆記（深入）”；
實現堆排序的核心在于理解堆的概念。堆是一種特殊的完全二叉樹，滿足堆屬性：父節點的值大于或等于（或小于或等于）其子節點的值。堆排序利用這個特性，通過構建最大堆（或最小堆）來排序元素。
首先，我們需要構建一個最大堆。假設我們有一個數組，我們可以從最后一個非葉子節點開始，向下調整節點，使其滿足最大堆的條件。
def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left arr[largest]: largest = left if right arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)
這個函數heapify的作用是將一個子樹調整為最大堆。從根節點開始，比較根節點與其左右子節點的值，如果子節點的值更大，則交換它們，并繼續向下調整，直到子樹滿足最大堆的條件。
構建好最大堆后，我們就可以進行排序了。排序的過程是將堆頂元素（最大值）與數組的最后一個元素交換，然后縮小堆的大小，再次調整堆頂，使其滿足最大堆的條件。這個過程重復，直到堆的大小為1。
def heap_sort(arr): n = len(arr) # 構建最大堆 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 一個個從堆中提取元素 for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr
在實際使用中，你可以這樣調用heap_sort函數：
arr = [12, 11, 13, 5, 6, 7] sorted_arr = heap_sort(arr) print(sorted_arr) # 輸出: [5, 6, 7, 11, 12, 13]
現在，讓我們談談堆排序的優劣以及一些需要注意的點。
優點：
- 時間復雜度為O(n log n)，無論最壞情況還是平均情況都表現良好。
- 堆排序是一種原地排序算法，除了輸入數組外，不需要額外的存儲空間。
缺點：
踩坑點：
- 在實現heapify函數時，容易忘記遞歸調用，導致堆調整不完全。
- 在構建最大堆時，容易忘記從最后一個非葉子節點開始調整，導致初始堆構建錯誤。
優化建議：
- 如果你需要穩定排序，可以考慮使用歸并排序或插入排序。
- 在處理小規模數據時，可以結合其他排序算法，如快速排序或插入排序，以提高整體性能。
通過這些經驗分享和深入思考，希望你能更好地理解和應用堆排序。無論是在面試中展示你的算法能力，還是在實際項目中優化性能，堆排序都是一個值得掌握的工具。
