一.堆的基本概念

1.什么是堆

堆是一種特殊的完全二叉樹，滿足一下性質：

• 最大堆：每個節點的值都大于或等于其子節點的值（堆頂元素最大）
• 最小堆：每個節點的值都小于或等于其子節點的值（堆頂元素最小）

其中，堆排序常使用最大堆來進行升序排序

?2.堆的存儲

堆常用數組進行存儲，對于數組中第i個元素：

• 父節點的位置：(i-1)/2
• 左節點的位置：2*i+1
• 右節點的位置：2*i+2

二、堆排序的基本思想

堆排序的基本思想分為兩個主要步驟：
1. 建堆：將無序數組構建成一個最大堆
2. 排序：重復從堆中取出最大元素（堆頂），然后調整剩余元素使其重新成為最大堆

三、堆排序的詳細步驟

?1. 構建最大堆
從最后一個非葉子節點開始（即n/2 - 1），向前依次對每個節點執行"下沉"操作，確保以該節點為根的子樹滿足堆的性質。

下沉操作：
1. 比較當前節點與其左右子節點
2. 如果當前節點小于某個子節點，則與較大的子節點交換
3. 繼續向下比較，直到當前節點大于等于其子節點或到達葉子節點

2. 排序過程
1. 將堆頂元素（最大值）與堆的最后一個元素交換
2. 堆的大小減1（排除已排序的元素）
3. 對新的堆頂元素執行下沉操作，恢復堆的性質
4. 重復上述過程，直到堆中只剩一個元素

演示：?

?

四、堆排序的代碼實現

#include<iostream>
#include<algorithm>using namespace std;//重建堆
void adjust(int a[],int start,int end)
{int temp=a[start];    //根節點for(int i=2*start+1;i<=end;i=i*2+1)   //從左子樹開始{if(i<end&&a[i]<a[i+1])    //如果右子樹大于左子樹，則i指向右子樹{i++;}if(a[i]>temp)    //如果子節點大于根節點，則將子節點的值賦給根節點{a[start]=a[i];start=i;}else    //如果子節點小于根節點，則跳出循環{break;}}a[start]=temp;    //將根節點的值賦給子節點
}//堆排序
void heapsort(int a[],int n)
{//建立大根堆for(int i=n/2-1;i>=0;i--)   //從最后一個非葉子節點開始{adjust(a,i,n-1);    //調整堆}//交換堆頂和堆底元素，重新調整堆for(int i=n-1;i>0;i--){swap(a[0],a[i]);    //交換堆頂和堆底元素adjust(a,0,i-1);    //調整堆}
}int main()
{int a[]={46,55,13,42,94,17,5,70};int n=sizeof(a)/sizeof(a[0]);heapsort(a,n);for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
}

五、堆排序的優缺點

優點：
1. 時間復雜度穩定為O(n log n)，沒有最壞情況
2. 空間復雜度低，是原地排序算法
3. 適合處理大規模數據

?缺點：
1. 不穩定排序算法（相同元素的相對位置可能改變）
2. 在數據量較小的情況下，常數因子較大，可能不如插入排序等簡單算法快
3. 數據訪問方式不夠局部化（緩存不友好）

六、堆排序的應用場景

1. 需要穩定O(n log n)時間復雜度的場景
2. 內存受限的環境（因為它是原地排序）
3. 需要同時進行插入和提取最大/最小值的場景（優先隊列）
4. 實時系統，因為最壞情況性能好