堆
這篇文章我們來手寫一下堆排序，首先我們來解釋一下什麼是堆？
堆是一種資料結構，需要滿足如下幾個特性
- 堆是一顆完全二叉樹（生成節點的順序是從左往右，從上往下依次進行）
- 堆中某個節點值總是不大于或者不小于其父節點的值
将根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆
大根堆和小根堆如下圖所示
假設有如下一個完全二叉樹，如何将它調整為一個堆呢？
可以看到10及其子節點符合條件，3及其子節點符合條件，4這個節點不符合條件。
是以要對4這個節點進行調整，調整的過程稱為heapify
- 從4這個節點的左右節點找一個大的節點（即10這個節點）和4這個節點進行交換
- 交換完有可能交換後的節點不符合條件，是以還需要進行調整（調整過程和1類似）