# 堆排序算法 > 原文： [https://www.programiz.com/dsa/heap-sort](https://www.programiz.com/dsa/heap-sort) #### 在本教程中，您將學習堆排序算法的工作原理。 此外，您還將找到使用 C，C++ ，Java 和 Python 進行堆排序的工作示例。 堆排序是計算機編程中一種流行且高效的排序算法。 學習如何編寫堆排序算法需要了解兩種類型的數據結構-數組和樹。 我們要排序的初始數字集存儲在一個數組中，例如`[10, 3, 76, 34, 23, 32]`，排序后，我們得到一個排序數組`[3,10,23,32,34,76]` 堆排序的工作原理是將數組的元素可視化為一種特殊的完全二叉樹，稱為堆。 前提條件是，您必須了解[完全二叉樹](/dsa/complete-binary-tree)和[堆數據結構](/dsa/heap-data-structure)。 * * * ## 數組索引和樹元素之間的關系 完全二叉樹具有一個有趣的屬性，我們可以用來查找任何節點的子代和父代。 如果數組中任何元素的索引為`i`，則索引`2i+1`中的元素將成為左子元素，而`2i+2`索引中的元素將成為右子元素。 同樣，索引為`i`的任何元素的父級都由`(i-1)/2`的下限給出。  數組和堆索引之間的關系 讓我們測試一下 ``` Left child of 1 (index 0) = element in (2*0+1) index = element in 1 index = 12 Right child of 1 = element in (2*0+2) index = element in 2 index = 9 Similarly, Left child of 12 (index 1) = element in (2*1+1) index = element in 3 index = 5 Right child of 12 = element in (2*1+2) index = element in 4 index = 6 ``` 我們還要確認規則是否適用于尋找任何節點的父節點 ``` Parent of 9 (position 2) = (2-1)/2 = ? = 0.5 ~ 0 index = 1 Parent of 12 (position 1) = (1-1)/2 = 0 index = 1 ``` 了解數組索引到樹位置的這種映射對于了解堆數據結構如何工作以及如何用于實現堆排序至關重要。 * * * ## 什么是堆數據結構？ 堆是一種特殊的基于樹的數據結構。 如果滿足以下條件，則據說二叉樹遵循堆數據結構： * 它是[完全二叉樹](/dsa/complete-binary-tree) * 樹中的所有節點都遵循其大于子節點的屬性，即最大元素位于根及其子節點且小于根，依此類推。 這樣的堆稱為最大堆。 相反，如果所有節點都小于其子節點，則稱為最小堆 以下示例圖顯示了最大堆和最小堆。  最大堆和最小堆 要了解更多信息，請訪問[堆數據結構](/dsa/heap-data-structure)。 * * * ## 如何對一棵樹“建堆” 從完全二叉樹開始，我們可以通過在堆的所有非葉元素上運行一個稱為`heapify`的函數，將其修改為最大堆。 由于`heapify`使用遞歸，因此可能很難掌握。 因此，讓我們首先考慮如何只用三個元素堆放一棵樹。 ``` heapify(array) Root = array[0] Largest = largest( array[0] , array[2*0 + 1]. array[2*0+2]) if(Root != Largest) Swap(Root, Largest) ```  建堆的基礎案例 上面的示例顯示了兩種情況-一種是根是最大的元素，而我們不需要做任何事情。 另一個根中有一個較大的子元素，我們需要交換以維護最大堆屬性。 如果您以前使用過遞歸算法，則可能已經確定這必須是基本情況。 現在讓我們考慮另一個場景，其中存在多個級別。  當其子樹已經是最大堆時，如何對根元素建堆 頂部元素不是最大堆，但是所有子樹都是最大堆。 為了保持整個樹的最大堆屬性，我們將不得不繼續向下推 2 直到它到達正確的位置。  當子樹為最大堆時如何對根元素建堆 因此，要在兩個子樹都是最大堆的樹中維護最大堆屬性，我們需要在根元素上重復運行`heapify`，直到它大于其子元素或成為葉節點為止。 我們可以將這兩個條件合并到一個`heapify`函數中 ``` void heapify(int arr[], int n, int i) { // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } } ``` 此函數適用于基本情況和任何大小的樹。 因此，只要子樹是最大堆，我們就可以將根元素移動到正確的位置，以保持任何樹大小的最大堆狀態。 * * * ## 建立最大堆 要從任何樹構建最大堆，我們可以從下至上開始對每個子樹進行堆放，并在將函數應用于包括根元素的所有元素后以最大堆結束。 在完整樹的情況下，非葉節點的第一個索引由`n/2 - 1`給出。 之后的所有其他節點都是葉節點，因此不需要進行堆放。 因此，我們可以建立一個最大堆 ``` // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); ```  創建數組并計算`i`  建立用于堆排序的最大堆的步驟  建立用于堆排序的最大堆的步驟  建立用于堆排序的最大堆的步驟 如上圖所示，我們首先堆放最小的最小樹，然后逐漸向上移動直到到達根元素。 恭喜，如果您到此為止都已經了解了所有內容，那么您就可以掌握堆方法了。 * * * ## 堆排序如何工作？ 1. 由于樹滿足最大堆屬性，因此最大的項存儲在根節點上。 2. **交換**：刪除根元素，并將其放在數組的末尾（第`n`個位置）。將樹的最后一項（堆）放在空白處。 3. **刪除**：將堆大小減小 1。 4. **建堆**：再次建堆根元素，以使我們的根元素最高。 5. 重復此過程，直到對列表中的所有項目進行排序為止。  交換，刪除和建堆 下面的代碼顯示了該操作。 ``` // Heap sort for (int i = n - 1; i >= 0; i--) { swap(&arr[0], &arr[i]); // Heapify root element to get highest element at root again heapify(arr, i, 0); } ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Heap Sort in 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("%d " % arr[i], end='') ``` ```java // Heap Sort in Java public class HeapSort { public void sort(int arr[]) { int n = arr.length; // Build max heap for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // Heap sort for (int i = n - 1; i >= 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // Heapify root element heapify(arr, i, 0); } } void heapify(int arr[], int n, int i) { // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } // Function to print an array static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // Driver code public static void main(String args[]) { int arr[] = { 1, 12, 9, 5, 6, 10 }; HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); } } ``` ```c // Heap Sort in C #include <stdio.h> // Function to swap the the position of two elements void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void heapify(int arr[], int n, int i) { // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) { swap(&arr[i], &arr[largest]); heapify(arr, n, largest); } } // Main function to do heap sort void heapSort(int arr[], int n) { // Build max heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i >= 0; i--) { swap(&arr[0], &arr[i]); // Heapify root element to get highest element at root again heapify(arr, i, 0); } } // Print an array void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) printf("%d ", arr[i]); printf("\n"); } // Driver code int main() { int arr[] = {1, 12, 9, 5, 6, 10}; int n = sizeof(arr) / sizeof(arr[0]); heapSort(arr, n); printf("Sorted array is \n"); printArray(arr, n); } ``` ```cpp // Heap Sort in C++ #include <iostream> using namespace std; void heapify(int arr[], int n, int i) { // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } // main function to do heap sort void heapSort(int arr[], int n) { // Build max heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i >= 0; i--) { swap(arr[0], arr[i]); // Heapify root element to get highest element at root again heapify(arr, i, 0); } } // Print an array void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) cout << arr[i] << " "; cout << "\n"; } // Driver code int main() { int arr[] = {1, 12, 9, 5, 6, 10}; int n = sizeof(arr) / sizeof(arr[0]); heapSort(arr, n); cout << "Sorted array is \n"; printArray(arr, n); } ``` * * * ## 堆排序復雜度 對于所有情況（最佳情況，平均情況和最壞情況），堆排序都具有`O(nlog n)`時間復雜度。 讓我們了解原因。 包含`n`個元素的完全二叉樹的高度為`log n` 如我們先前所見，要完全堆積其子樹已經是最大堆的元素，我們需要繼續比較該元素及其左，右子元素，并將其向下推，直到其兩個子元素均小于其大小。 在最壞的情況下，我們需要將元素從根節點移到葉節點，進行多次`log(n)`比較和交換。 在`build_max_heap`階段，我們對`n/2`元素執行此操作，因此`build_heap`步驟的最壞情況復雜度為`n/2*log n ~ nlog n`。 在排序步驟中，我們將根元素與最后一個元素交換并堆放根元素。 對于每個元素，這又要花費`log n`最壞的時間，因為我們可能必須將元素從根到葉一直帶到最遠。 由于我們將此重復`n`次，因此`heap_sort`步驟也是`nlog n`。 同樣，由于`build_max_heap`和`heap_sort`步驟是一個接一個地執行的，因此算法復雜度不會增加，而是保持在`nlog n`的順序。 它還在`O(1)`空間復雜度中執行排序。 與快速排序相比，它具有更好的最壞情況`( O(nlog n) )`。 對于最壞的情況，快速排序具有復雜度`O(n^2)`。 但是在其他情況下，快速排序速度很快。 `Introsort`是堆排序的替代方案，它組合了快速排序和堆排序以保留兩者的優勢：最壞情況下的堆排序速度和平均速度。 * * * ## 堆排序應用 涉及安全性的系統和嵌入式系統（例如 Linux Kernel）使用堆排序，因為堆排序的運行時間上限為`O(n log n)`，輔助存儲的上限為`O(1)`上限。 盡管即使在最壞的情況下，堆排序也具有`O(n log n)`時間復雜度，但它沒有更多的應用（與其他排序算法（如快速排序，歸并排序）相比）。 但是，如果我們要從項目列表中提取最小（或最大）的數據，而無需保持其余項目按排序順序的開銷，則可以有效地使用其基礎數據結構堆。 例如，優先隊列。