---
# System prepended metadata

title: 堆積排序(Heapsort)

---

# 堆積排序(Heapsort)
1. 堆積排序是利用堆這種資料結構而設計的一種排序演算法，堆排序是一種選擇排序，它的最壞、最好、平均時間複雜度均為 `O(nlogn)`，它也是**不穩定排序**。
2. 堆(Heap)是具有以下性質的完全二元樹：每個節點的值都大於或等於其左右孩子結點的值，稱為大頂堆，注意：沒有要求節點的左孩子的值和右孩子的值的大小關係。
3. 每個節點的值都小於或等於其左右孩子節點的值，稱為小頂堆。

## 基本介紹

### 大頂堆

**示意圖**

![](https://www.namepluto.com/wp-content/uploads/2021/06/%E5%9B%BE%E7%89%872.png)

我們對堆中的節點按層進行編號，映射到陣列中就是下面這個樣子: 

![](https://www.namepluto.com/wp-content/uploads/2021/06/image-65.png)

特點：
```java=
arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]  // i 對應第幾個節點，i從0開始編號
```

### 小頂堆

**示意圖**
![](https://www.namepluto.com/wp-content/uploads/2021/06/%E5%9B%BE%E7%89%873.png)

特點：
```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]`，將之構造成一個大頂堆。

![](https://i.imgur.com/LxgTCDz.png)

2. 先找到最後一個葉子開始(葉子節點無須調整，第一個非葉子節點 `(arr.length/2) - 1 = 5/2 -1 = 1`，也就是 6 節點)，**從左至右，從下至上**調整。`[6, 5, 9]` 中 9 最大，將之與 6 交換。

![](https://www.namepluto.com/wp-content/uploads/2021/06/c2-1.png)

3. 接著找到第二個非葉子節點，也就是 4 節點，`[4, 9, 8]`中 9 最大，將之與 4 交換。

![](https://www.namepluto.com/wp-content/uploads/2021/06/c3-1.png)

4. 剛剛交換了 4 和 9 之後導致子根 `[4, 5, 6]` 結構混亂，繼續調整，將最大的 6 和 4 節點交換。

![](https://www.namepluto.com/wp-content/uploads/2021/06/c4-1.png)

此時就將無序陣列構造成了大頂堆。

### 步驟二
將堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素，如此反覆進行交換、重建、交換。

1. 將堆頂元素 9 和末尾元素 4 進行交換。

![](https://www.namepluto.com/wp-content/uploads/2021/06/a1.png)

2. 重新調整結構，使其繼續滿足堆定義。

![](https://www.namepluto.com/wp-content/uploads/2021/06/a2.png)

3. 再將堆頂元素 8 與末尾元素 5 進行交換，得到第二大元素 8。

![](https://www.namepluto.com/wp-content/uploads/2021/06/a3.png)

4. 後續過程，繼續進行調整、交換，如此反覆進行，最終使得整個序列有序。

![](https://www.namepluto.com/wp-content/uploads/2021/06/a4.png)

## 程式碼實現

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)