# 堆積排序
> 上一篇文章　[Euler路徑與Euler圖](https://hackmd.io/@iDoNotWantToCoding/Hydgjiaske)
> 下一篇文章　無
> 先備知識　　無
> 延伸閱讀　　無
---
## <font size=6>前言</font>
在了解堆積排序之前，我們需要了解以下幾個概念。
### 圖論的基礎概念
>傳送門:point_right:[圖論基礎觀念](/CbclZG4dSyuVAtq1YOEt8A)

### 二元樹(binary tree)
二元樹是資料結構與演算法中最重要的工具之一。與一般的樹結構不同，二元樹的每個節點最多只能有兩個子節點，分別稱為左子樹與右子樹。也就是說，在二元樹中，每個節點的子節點數量上限為兩個，並具有明確的左右之分。

### 完整二元樹(complete binary tree)
完整二元樹屬於二元樹的一種，該二元樹除了最後一層的節點，其他層的節點皆為全滿的狀態，如果最後一層的節點沒有全滿的話則靠左。
>要注意的是 **完整二元樹(complete binary tree)** 與 **滿二元樹(full binary tree)** 概念不相同，許多人容易搞混。
>
>> #### 完整二元樹(complete binary tree)：
>> 除了最後一層的節點，其他層的節點皆為全滿的狀態
>
>> #### 滿二元樹(full binary tree)：
>> 除了樹葉以外，每個節點都有兩個小孩。

### 堆序性(Heap Order Property)
>#### 最大堆(Max-Heap)：
>每個節點的值都**大於等於**其子節點的值。
>#### 最小堆(Min-Heap):
>每個節點的值都**小於等於**其子節點的值。
## <font size=6>概述</font>
堆積排序(Heap Order Property)是一種以 **堆(Heap)** 的資料結構進行排序演算法的方式，堆是一種特殊的完整二元樹，其中按照堆序性分為 **最大堆(Max-Heap)** 以及 **最小堆(Min-Heap)**。

### 堆積排序可以分成以下兩個步驟。
> ### 建構最大堆或最小堆
> #### 使用list作為建堆的架構，其中list與堆的樹架構之關係為：
> **父節點(Parent)**：`index` = (i - 1) // 2
> **左子節點(Left Child)**：`index` = 2 * i + 1
> **右子節點(Right Child)**：`index` = 2 * i + 2
>
> **範例**：`list` = [10, 5, 3, 2, 1]
> 
>
> 以下以建構最大堆為範例，將原始無序陣列轉換成最大堆，確保父節點 ≥ 子節點。
> ```python=
> def heapify(arr, n, i):
> largest = i # 假設目前的節點為最大值
> left = 2 * i + 1 # 左子節點
> right = 2 * i + 2 # 右子節點
>
> # 比較左子節點與父節點
> if left < n and arr[left] > arr[largest]:
> largest = left
>
> # 比較右子節點與目前最大值
> if right < n and arr[right] > arr[largest]:
> largest = right
>
> # 如果最大值不是父節點，交換並遞迴 heapify
> if largest != i:
> arr[i], arr[largest] = arr[largest], arr[i] # 交換
> heapify(arr, n, largest)
> ```
>
> ### 排序
> 在建構完成之後，`list`中的第0個元素必定會是資料中最大的數值。之後將這個最大的數值與末端的數進行交換，此時這個最大的數就是已經被排序完成的狀態，之後忽略它並且對其他數值進行重新建堆，**重複這個建堆以及交換的過程，最後就可以完成排序了**。
> ```python=18
> def heap_sort(arr):
> n = len(arr)
>
> # 第一步：建構最大堆
> for i in range(n // 2 - 1, -1, -1): # 從最後一個非葉節點往上 heapify
> heapify(arr, n, i)
>
> # 第二步：排序過程
> for i in range(n - 1, 0, -1):
> arr[0], arr[i] = arr[i], arr[0] # 將最大值移至末端
> heapify(arr, i, 0) # 對新的堆頂元素進行 heapify
>```
>
> #### 以`list` = [10, 5, 3, 2, 1]為例
> 1. 初始陣列：[4, 10, 3, 5, 1]
> 2. 建構最大堆：[10, 5, 3, 4, 1]
> 3. 取最大值10放到末尾：[1, 5, 3, 4, 10]
> 4. 重新建堆： [5, 4, 3, 1, 10]
> 5. 重複交換及建堆：[1, 4, 3, 5, 10]
> 6. 最後結果：[1, 3, 4, 5, 10]
## <font size=6>範例題目</font>
在了解堆積排序的基本排序概念後，我們可以將它連接一些實際的例子以幫助我們熟悉。
將堆積排序實際運用在撲克牌的題目：Hand of Straights
> ### Straights是什麼？Straights的成立條件？
> Straights的中文名稱稱為"順子"，在德州撲克、大老二等鋪克牌遊戲中運用。
> 順子的成立條件為五張牌的數子相連，其中`A`只能出現在兩端不可出現在中間。

### 題目敘述：
> 愛麗絲有一定數量的卡片，她想將這些卡片重新排列成群組，使得每組大小為 `groupSize`，並由 `groupSize` 張連續的卡片組成。
>
>給定一個整數陣列 `hand`，其中 `hand[i]` 是第 i 張卡片上寫的值和一個整數 `groupSize`，如果她可以重新排列卡片，則傳回 `True`，否則傳回 `False`。
>
在此題目中的順子並不局限於必須要五張相連號碼的牌，可以從`input`中的`groupSize`決定出一組順子需要幾張相連號碼的牌。

### 解題思路
1. 首先我們可以分析手中的牌數量是否為`groupSize`的倍數，如果不是的話，則無法完成分組，直接回傳`False`即可。

         # 張數不是 groupSize 的倍數，一定不可能分組
        if len(hand) % groupSize != 0:
            return False

2. 使用`Counter`來計算每個號碼的數量。

         # 統計每張牌的數量
        count = collections.Counter(hand)

3. 使用Min-Heap由小至大牌序陣列`hand`中的撲克牌。

        # 將所有出現過的牌放入最小堆
        min_heap = list(count.keys())
        heapq.heapify(min_heap)

4. 選出最小的牌，並且向後看`groupSize`張牌是否能形成順子，若不能滿足順子，則直接回傳`False`。

             first = min_heap[0]  # 最小牌作為一組的起點
            for i in range(first, first + groupSize):
                if count[i] == 0:
                    return False  # 某張牌不夠用

5. 形成順子後，將成員的`count`全部減1，如果剩餘的`count`為0則直接刪除。

                 count[i] -= 1
                if count[i] == 0:
                    # 如果此牌用完了，且正是 heap 頂部，從 heap 移除
                    if i == min_heap[0]:
                        heapq.heappop(min_heap)

6. 回到第4步繼續檢查是否形成順子，直到`min heap`中的牌全部清空則回傳`True`。

### 完整程式碼

import collections
import heapq

class Solution(object):
    def isNStraightHand(self, hand, groupSize):
        # 張數不是 groupSize 的倍數，一定不可能分組
        if len(hand) % groupSize != 0:
            return False

        # 統計每張牌的數量
        count = collections.Counter(hand)

        # 將所有出現過的牌放入最小堆
        min_heap = list(count.keys())
        heapq.heapify(min_heap)

        while min_heap:
            first = min_heap[0]  # 最小牌作為一組的起點
            for i in range(first, first + groupSize):
                if count[i] == 0:
                    return False  # 某張牌不夠用
                count[i] -= 1
                if count[i] == 0:
                    # 如果此牌用完了，且正是 heap 頂部，從 heap 移除
                    if i == min_heap[0]:
                        heapq.heappop(min_heap)

        return True

:::spoiler 額外補充(點我展開)
`heapq`為python內建標準函式庫中的一部分。
可以使用`heapq.heapify(lst)`直接進行最小堆排序。
:::

---
> 上一篇文章　[Euler路徑與Euler圖](https://hackmd.io/@iDoNotWantToCoding/Hydgjiaske)
> 下一篇文章　無
> 先備知識　　無
> 延伸閱讀　　無
> 觀念是非題　[圖論觀念是非題](https://docs.google.com/forms/d/e/1FAIpQLSfynh26cxO2G8SfBJrqFgO9_2BrMKEYtRbYspk3yM0djuzzEQ/viewform?usp=header)