🌟個人博客：www.hellocode.top
🏰Java知識導航：Java-Navigate
🔥CSDN：HelloCode.
🌞知乎：HelloCode
🌴掘金：HelloCode
?如有問題，歡迎指正，一起學習~~
堆排序是一種高效的排序算法，基于堆數據結構實現。堆是一種特殊的樹狀結構，具有以下特點：父節點的值大于等于（或小于等于）其子節點的值。堆排序利用堆的性質，將數組看作一個完全二叉樹，通過構建最大堆（或最小堆），實現對數組的排序。
基本思想
這里采用五分鐘學算法大佬的圖解，十分清晰
- 構建初始堆：將待排序數組視為一個完全二叉樹，從最后一個非葉子節點開始，逐步將樹調整為大頂堆（或小頂堆）。
- 排序過程：將堆頂元素與最后一個葉子節點交換，然后將堆大小減一，繼續調整堆結構，使其重新成為大頂堆（或小頂堆）。
- 重復步驟 2，直到堆大小為 1，排序完成。
需要掌握的部分知識：
- 完全二叉樹：指除了最后一層外，其他層的節點都被完全填滿，最后一層的節點都靠左排列，并且不存在不規則的空缺。這意味著從根節點到倒數第二層都是滿的，最后一層從左到右有可能存在空缺，但不能跳過空缺。
- 堆：堆是一種基于完全二叉樹的數據結構，可分為大頂堆和小頂堆。在大頂堆中，父節點的值大于等于其子節點的值；在小頂堆中，父節點的值小于等于其子節點的值。堆的性質使其適合用來進行排序和實現優先隊列等數據結構。
- 堆的構建和調整：在堆排序中，我們主要關注構建初始堆和調整堆的過程。構建初始堆的目標是將一個無序數組調整為一個最大堆或最小堆。調整堆的目標是保持堆的性質，確保父節點的值大于等于（或小于等于）子節點的值。
- 完全二叉樹中相關計算：對于任意節點來說，左子節點索引計算公式為
2*i + 1，右子節點為：2*i + 2，最后一個非葉子節點計算公式為n/2 - 1（n為節點總數，i為當前節點索引）
這里的難點就是對應的概念和計算，拿到待排序數組后，首先需要將其構建為大頂堆（或小頂堆），然后需要進行相應的節點交換，并繼續調整結構使其保持大頂堆（或小頂堆）特性，代碼層面還需要配合動畫多多理解
代碼實現
相比之前的幾種排序，堆排序就相對復雜一些，需要用到遞歸的思想。遇到遞歸，還是要考慮遞歸的出口，避免無休止的遞歸，這里使用遞歸就是不斷調整來維持堆結構，自上而下遞歸，那么遞歸的出口就是到葉子節點（不能超出數組范圍）。
主要分為三個方法：heapSort（對外提供的堆排序方法）、buildMaxHeap（構建初始堆結構方法）、heapify（真正調整堆結構、維持堆規則的方法）
package top.hellocode;import java.util.Arrays;/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月13日 20:01*/
public class HeapSort {public static void main(String[] args) {int[] arr = {19, 23, 13, 7, 84, 66, 98, 78, 54, 32, 23, 77, 88, 17};System.out.println("排序前：" + Arrays.toString(arr));heapSort(arr);System.out.println("排序后：" + Arrays.toString(arr));}public static void heapSort(int[] arr) {// 構建初始堆結構（默認大頂堆，實現升序排序）buildMaxHeap(arr, arr.length);// 開始排序// 從堆頂取出元素，并和最后一個元素進行交換，并不斷調整維持堆結構for (int i = arr.length - 1; i > 0; i--) {int temp = arr[i];arr[i] = arr[0];arr[0] = temp;heapify(arr, 0, i);}}// 構建初始最大堆private static void buildMaxHeap(int[] arr, int length) {// 構建大頂堆，從最后一個非葉子節點開始（(length - 1) / 2）for (int i = length / 2 - 1; i >= 0; i--) {heapify(arr, i, length);}}/*** 調整堆結構，使其成為最大堆* int[] arr：待調整數組* int index：子樹根節點（從哪里開始向下調整）* int length：數組長度，主要用來判斷子樹遞歸是否到達了葉子節點（超出數組長度）*/private static void heapify(int[] arr, int index, int length) {// 默認假設當前子樹根節點為最大值，尋找左右子節點是否有更大值int max = index;int left = 2 * index + 1;int right = 2 * index + 2;// 遞歸終止條件（出口）if (left >= length || right >= length) {return;}// 開始比較左右子節點if (arr[left] > arr[max]) {max = left;}if (arr[right] > arr[max]) {max = right;}// 如果最大值發生了變化，則進行交換// 只要是有交換發生，就需要對其子樹繼續進行遞歸調整if (max != index) {int temp = arr[index];arr[index] = arr[max];arr[max] = temp;// 繼續對其子樹遞歸調整heapify(arr, max, length);}}
}
測試：
排序前：[19, 23, 13, 7, 84, 66, 98, 78, 54, 32, 23, 77, 88, 17]
排序后：[7, 13, 17, 19, 23, 23, 32, 54, 66, 77, 78, 84, 88, 98]
優化
堆排序的核心是構建堆和調整堆，可以通過一些優化來提升性能。
- 在構建堆的時候，有自頂向上和自底向下兩種，不同的場景使用不同的方法性能也有不同，這里可以去了解了解，對對應的場景進行優化。
總結
優點
- 高效性：堆排序的時間復雜度為 O(n log n)，在大規模數據下表現優異。
- 不占用額外空間：堆排序是原地排序算法，不需要額外的存儲空間。
缺點
- 不穩定性：堆排序是不穩定的排序算法，相等元素的相對順序在排序后可能發生變化。
復雜度
- 時間復雜度
- 平均時間復雜度：O(n log n)
- 最好情況時間復雜度：O(n log n)
- 最壞情況時間復雜度：O(n log n)
- 空間復雜度：原地排序，空間復雜度為 O(1)。
使用場景
堆排序適用于大規模數據的排序，尤其在需要穩定排序時（如堆頂元素是最大值時）。雖然實現相對復雜，但其高效性使其成為處理大量數據的有力工具。在實際應用中，堆排序在需要高性能排序時可能是一個不錯的選擇。
當使用堆排序時，應特別注意其時間和空間復雜度的說明是基于固定的數據集。在實際情況中，堆排序的性能可能因為一些特定因素而有所不同，因此在特定情況下堆排序可能表現更好。
)
)
