---
tags: 演算法, LeetCode
disqus: HackMD
---

# 堆積排序(Heap Sort)

在提到堆積排序前我們先講講樹的資料結構，因為在堆積排序中會使用到某一種樹。

## 樹-資料結構

那樹是甚麼

* 抽象資料類型
* 被用來模擬分層資料結構
* 無循環`graph`

在樹當中只會有一個`root value`，也就是樹根，看到下面那張圖`7,5,6,9`都有`Subtree`(子樹)，每個圈圈我們稱它為`node`(節點)，箭頭稱為`edge`，以圖片藍色圈起來的子樹為例，`7`就是`2, 10, 6`的`parent node`，而`2, 10, 6`就是`7`的`children node`。


### 二元樹(Binary Tree)

在樹的資料結構中有許多不同的樹，最常見的樹為二元樹。

二元樹中也有不同種類

(Types of Binary Tree || Designed by [Anand K Parmar](https://medium.com/@anandkparmar))

#### 1. Full Binary Tree

`Full Binary Tree` 每個節點都有 0 或 2 個子節點


#### 2. Complete Binary Tree

`Complete Binary Tree` 除了最後一層外，所有層節點都是滿的，在最後一層中，節點盡可能位於左側


#### 3. Degenerate(or Pathological) Binary Tree

`Degenerate(or Pathological) Binary Tree` 每個父節點只會有一個子節點

#### 4. Perfect Binary Tree

`Perfect Binary Tree` 內部節點都有兩個子節點，並且左右都處於相同深度

#### 5. Balanced Binary Tree

`Balanced Binary Tree` 每個節點的左右子樹的高度最多相差1的二元樹

### Max Heap

`max heap` 就是這次排序中會使用到的資料結構

* 是一個 `Complete Binary Tree`
* `SubTree` 的 `root` 一定會是最大

(圖片來自[Binary heap](https://en.wikipedia.org/wiki/Binary_heap))

## 堆積排序介紹

先將數組轉換成`Complete Binary Tree`資料結構，再換成`Max Heap`，這時`root`值將會是最大值，將`root`值移出去，再繼續將樹轉換成`Max Heap`，依此類推，這就是堆積排序。

([圖片來源](https://commons.wikimedia.org/wiki/File:Heapsort-example.gif))

## 虛擬碼

首先是建立`Max Heap` 的`pseudo code`

> heapSize 和 arr 為全域變數，因為在多個function中使用

虛擬碼中，`heapSize` 的值為數組 `arr` 的長度减 `1`。然後，有一個迴圈從 `heapSize / 2` 開始，遍歷所有的非葉子節點，至第 `0` 個節點。

每個非葉子節點會被傳遞給 `MAX-HEAPIFY` 函數。`MAX-HEAPIFY` 函數的作用是使其成為`max heap`，使得父節點的鍵值都大於等於其子節點的鍵值。

經過這段虛擬碼的執行後，數組 `arr` 會被轉化成一個`max heap`。

BUILD-MAX-HEAP():
    heapSize = arr.length - 1
    for i from (heapSize / 2) to 0:
        arr = MAX-HEAPIFY(i)

這個虛擬碼做的事是在給定的節點`i`的子樹中，找到最大的節點並使之成為`i`的父節點。

> 最多走 $log2^n$層，這邊的`n`為`node`數量，假設有`1024`個`node`代表樹為`10`層

以下是該虛擬碼的詳細說明：

1. `2，3`行計算`i`節點的左右子節點在陣列中的位置。

3. `4，5`行
如果左子節點存在且大於根節點，那麼將左子節點設為最大值。

3. `8，9`行。
如果右子節點存在且大於當前的最大值，那麼將右子節點設為最大值。

1. `10~12`行。如果最大值不是根節點，則交換根節點和最大值並遞迴調用`MAX-HEAPIFY(largest`)保持`max heap`的性質。

這個 `MAX-HEAPIFY` 作用是將某一個節點下面的子樹調整成最大堆，並且讓根節點是最大值。

// BigO O(logn)
MAX-HEAPIFY(i):
    l = 2 * i + 1
    r = 2 * i + 2
    if l <= heapSize and arr[l] > arr[i]:	
        largest = l
    else:
        largest = i
    if r <= heapSize and arr[r] > arr[largest]:	
        largest = r
    if largest is not i:	
        swap arr[i] with arr[largest]	
        MAX-HEAPIFY(largest)

我們舉例`arr = [8, 6, 2, 4, 5, 3, 7]`，`heapSize` 就會等於 `6`，接著下來跑迴圈先給予`i=3`但`arr[3]`底下沒有節點，所以舉`i=2`為例子，丟進`MAX-HEAPIFY`，接下來往下看

假設`i` 為 `2`，這時候 `l = 5`, `r = 6`，將虛擬碼帶入數字


這邊可以看到找到最大值的`index`等於`6`，所以我們跟`i`位置的值交換位置，那他會從`largest`的位置再往下查看是否為最大值，如果不是就會再持續交換


再來才是本篇重點`Heap sort`的`pseudo code`，一開始創建`max heap`後將最大值與陣列最後一個值互換，這樣就能確保最後一個值為最大值，依照此步驟，依此類推，就可以完成陣列的排序。

HEAP-SORT():
    BUILD-MAX-HEAP(arr)
    for i from arr.length - 1 to 0:
        exchangeArr[0] with arr[i]
        heapSize = heapSize - 1
        MAX-HEAPIFY(0)

如下圖步驟循環

1. 將資料建立成一個`max heap`。
1. 將根節點`(root)`與最後一個節點交換，並將最後一個節點刪除。
1. 重新調整`heap`，使其成為一個`max heap`。
1. 重複步驟 `2` 和 `3`，直到`heap`中只剩下一個節點。


## 複雜度

### 時間複雜度為
$O(n log n)$

### 空間複雜度為
$O(1)$

## `Heap Sort`程式碼

class HeapSort{
    constructor(arr){
        this.arr = arr;
        this.heapSize = arr.length;
    }

    buildMaxHeap(){
        this.heapSize = this.heapSize - 1;
        for(let i = Math.floor(this.heapSize/2); i >= 0; i--){
            this.maxHeapify(i);
        }
    }

    maxHeapify(i){
        let left = 2*i + 1;
        let right = 2*i + 2;
        let largest;

        if(left <= this.heapSize && this.arr[left] > this.arr[i]){
            largest = left;
        } else {
            largest = i;
        }

        if(right <= this.heapSize && this.arr[right] > this.arr[largest]){
            largest = right;
        }

        if(largest != i){
            let temp = this.arr[i];
            this.arr[i] = this.arr[largest];
            this.arr[largest] = temp;
            this.maxHeapify(largest);
        }
    }

    sort(){
        this.buildMaxHeap();
        for(let i = this.arr.length-1; i >= 0; i--){
            let temp = this.arr[0];
            this.arr[0] = this.arr[i];
            this.arr[i] = temp;
            this.heapSize--;
            this.maxHeapify(0);
        }
    }
}

let arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
let heap = new HeapSort(arr);
heap.sort();

console.log(heap.arr); // [1, 2,  3,  4,  7, 8, 9, 10, 14, 16]

## LeetCode實戰

[912. Sort an Array](https://leetcode.com/problems/sort-an-array)

給你一個整數陣列`nums`，請將陣列以升序排列並返回。您必須在`O(nlog(n))`時間複雜度內解決此問題，並使用較小的空間複雜度。


[☑解法詳解](https://leetcode.com/problems/sort-an-array/solutions/3059335/javascript-heap-sort-solution-best-77/)

### code:tada:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    let heapSize;

    function maxHeapify(i){
        let left = 2*i + 1;
        let right = 2*i + 2;
        let largest;

        if(left <= heapSize && nums[left] > nums[i]){
            largest = left;
        } else {
            largest = i;
        }

        if(right <= heapSize && nums[right] > nums[largest]){
            largest = right;
        }

        if(largest != i){
            let temp = nums[i];
            nums[i] = nums[largest];
            nums[largest] = temp;
            maxHeapify(largest);
        }
    }

    function buildMaxHeap(){
        heapSize = nums.length - 1;
        for(let i = Math.floor(heapSize/2); i >= 0; i--){
            maxHeapify(i);
        }
    }

    buildMaxHeap();
    for(let i = nums.length-1; i >= 0; i--){
        let temp = nums[0];
        nums[0] = nums[i];
        nums[i] = temp;
        heapSize--;
        maxHeapify(0);
    }
    return nums
};

### Submissions


## 來源

[資料結構與演算法 (JavaScript)](https://www.udemy.com/course/algorithm-data-structure/)

> [name=@joe94113] [time=Tue, JAN 15, 2023 10:00 PM] [color=#907bf7]