# Heap - 堆 一般情況下，堆通常指的是**二叉堆**，**二叉堆**是一個近似**完全二叉樹**的數據結構，**即披著二叉樹羊皮的數組，**故使用數組來實現較為便利。子結點的鍵值或索引總是小于（或者大于）它的父節點，且每個節點的左右子樹又是一個**二叉堆**(大根堆或者小根堆)。根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。**常被用作實現優先隊列。** ### 特點 1. **以數組表示，但是以完全二叉樹的方式理解**。 1. 唯一能夠同時最優地利用空間和時間的方法——最壞情況下也能保證使用 2NlogN2N \log N2NlogN 次比較和恒定的額外空間。 1. 在索引從0開始的數組中： - 父節點 `i` 的左子節點在位置`(2*i+1)` - 父節點 `i` 的右子節點在位置`(2*i+2)` - 子節點 `i` 的父節點在位置`floor((i-1)/2)` ### 堆的基本操作 以大根堆為例，堆的常用操作如下。 1. 最大堆調整（Max_Heapify）：將堆的末端子節點作調整，使得子節點永遠小于父節點 1. 創建最大堆（Build_Max_Heap）：將堆所有數據重新排序 1. 堆排序（HeapSort）：移除位在第一個數據的根節點，并做最大堆調整的遞歸運算 其中步驟1是給步驟2和3用的。