# 堆積排序(Heapsort)
1. 堆積排序是利用堆這種資料結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞、最好、平均時間複雜度均為 `O(nlogn)`，它也是**不穩定排序**。
2. 堆(Heap)是具有以下性質的完全二元樹：每個節點的值都大於或等於其左右孩子結點的值，稱為大頂堆，注意：沒有要求節點的左孩子的值和右孩子的值的大小關係。
3. 每個節點的值都小於或等於其左右孩子節點的值，稱為小頂堆。
## 基本介紹
### 大頂堆
**示意圖**
我們對堆中的節點按層進行編號，映射到陣列中就是下面這個樣子:
特點：
```java=
arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 對應第幾個節點，i從0開始編號
```
### 小頂堆
**示意圖**
特點：
```java=
arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 對應第幾個節點，i從0開始編號
```
一般升冪採用大頂堆，降冪採用小頂堆。
## 基本思想
1. 將待排序序列構造成一個大頂堆。
2. 此時，整個序列的**最大值**就是堆頂的根節點。
3. 將其與末尾元素進行交換，此時末尾就為最大值。
4. 然後將剩餘`n-1`個元素重新構造成一個堆，這樣會得到 `n` 個元素的次小值。如此反復執行，便能得到一個有序序列了。
可以看到在構建大頂堆的過程中，元素的個數逐漸減少，最後就得到一個有序序列了。
## 舉例說明
給你一個陣列 `[4, 6, 8, 5, 9]`，要求使用堆積排序法，將陣列**升冪**排序。
### 步驟一
構造初始堆，將給定無序陣列構造成一個大頂堆。
1. 給定一無序原始陣列 `[4, 6, 8, 5, 9]`，將之構造成一個大頂堆。
2. 先找到最後一個葉子開始(葉子節點無須調整，第一個非葉子節點 `(arr.length/2) - 1 = 5/2 -1 = 1`，也就是 6 節點)，**從左至右，從下至上**調整。`[6, 5, 9]` 中 9 最大，將之與 6 交換。
3. 接著找到第二個非葉子節點，也就是 4 節點，`[4, 9, 8]`中 9 最大，將之與 4 交換。
4. 剛剛交換了 4 和 9 之後導致子根 `[4, 5, 6]` 結構混亂，繼續調整，將最大的 6 和 4 節點交換。
此時就將無序陣列構造成了大頂堆。
### 步驟二
將堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素，如此反覆進行交換、重建、交換。
1. 將堆頂元素 9 和末尾元素 4 進行交換。
2. 重新調整結構，使其繼續滿足堆定義。
3. 再將堆頂元素 8 與末尾元素 5 進行交換，得到第二大元素 8。
4. 後續過程，繼續進行調整、交換，如此反覆進行，最終使得整個序列有序。
## 程式碼實現
1. 首先將陣列構造成大頂堆：
```java=
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args){
int arr[] = {4, 6, 8, 5, 9};
heapSort(arr);
}
public static void heapSort(int arr[]) {
System.out.println("堆積排序");
// 第一次調整
adjustHeap(arr, 1, arr.length);
System.out.println(Arrays.toString(arr));
// 第二次調整
adjustHeap(arr, 0, arr.length);
System.out.println(Arrays.toString(arr));
}
/**
* 功能：完成 將 i 對應的非葉子節點的子樹調整成大頂堆
* 舉例：int arr[] = {4, 6, 8, 5, 9} , i = 1 => adjustHeap 得到 {4, 9, 8, 5, 6}
* 如果我們再次調用 adjustHeap 傳入的是 i = 1 => 得到 {4, 9, 8, 5, 6} => {9, 6, 8, 5, 4}
* @param arr 待調整的陣列
* @param i 表示非葉子節點在陣列中的索引
* @param length 表示對多少個元素進行調整, length是在逐漸的減少
*/
// 將一個陣列(二元樹), 調整成一個大頂堆
public static void adjustHeap(int arr[], int i, int length) {
int temp = arr[i]; // 先取出當前元素的值, 保存在臨時變數
// 開始調整
// int k = i * 2 + 1 => i 的左子節點
// k = k * 2 + 1 => 下次再調的話就是下面的左子節點
for(int k = i * 2 + 1; k < length ; k = k * 2 + 1) {
if(k+1 < length && arr[k] < arr[k+1]) { // 左子節點小於右子節點
k++; // k 指向右子節點(因為要找到最大值)
}
if(arr[k] > temp) { // 如果子節點大於父節點
arr[i] = arr[k]; // 把較大的值賦給當前值
i = k; // i 指向 k 繼續循環比較
} else {
break;
}
}
arr[i] = temp; // 將 temp 值放到調整後的位置
}
}
```
output
```java=
堆積排序
[4, 9, 8, 5, 6]
[9, 6, 8, 5, 4]
```
2. 完善 `heapSort()` 方法，使之能排序為**有序陣列**：
```java=
public static void heapSort(int arr[]) {
int temp = 0;
System.out.println("堆積排序");
// 將無序序列構建成一個堆, 根據升序降序需求選擇大頂堆或小頂堆
// arr.length / 2 - 1 => 從下至上 由左至右 找出非葉子節點
for(int i = arr.length / 2 - 1; i >= 0; i--) {
// [4, 6, 8, 5, 9] => [4, 9, 8, 5, 6] => [9, 6, 8, 5, 4]
adjustHeap(arr, i, arr.length);
}
// 此時 [9, 6, 8, 5, 4]
// 將堆頂元素與末尾元素交換, 將最大元素移到陣列末端 [9, 6, 8, 5, 4] => [4, 6, 8, 5, 9]
// 重新調整結構, 使其滿足堆定義, 然後繼續交換堆頂元素與當前末尾元素, 反覆執行調整+交換, 直到整個序列有序
for(int j = arr.length - 1; j > 0; j--) {
// 交換
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
System.out.println(Arrays.toString(arr));
}
```
output
```java=
堆積排序
[4, 5, 6, 8, 9]
```
### 速度測試
同樣亂數產生八萬筆資料來試試堆積排序的速度：
```java=
public static void main(String[] args){
int arr[] = new int[80000];
for(int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random() * 80000);
}
Instant startTime = Instant.now();
// int arr[] = {4, 6, 8, 5, 9};
heapSort(arr);
Instant endTime = Instant.now();
System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}
```
output
```java=
共耗時：7 毫秒
共耗時：7 毫秒
共耗時：9 毫秒
共耗時：8 毫秒
共耗時：7 毫秒
```
使用堆積排序陣列數值，八萬筆資料平均只需 7.6 ms。
## 時間複雜度
假設今天要對一陣列使用堆積排序法由小到大排序。
### 最佳：O(n)
排序的元素值都一樣
### 平均：O(nlogn)
### 最差：O(nlogn)
Sign in with Wallet
Connect another wallet