堆

堆是完全二叉樹，一個大小為n的堆為一棵包含n個節點的完全二叉樹。完全二叉樹的根稱為堆頂。當堆中每個節點的關鍵字值大于等于其雙親節點的關鍵字值，這樣的堆稱為最小堆，當子節點的值都小于等于其父節點時，稱為最大堆。

使用數組來儲存堆中元素。對于數組中的i節點，其子節點為 2i +1 和2i + 2。則由此可以輕松的判斷節點之間的關系。然後我們考慮最小堆的具體情況。

然後考慮堆的向下調整運算AdjustDown(T heap[],int r,int j)。在堆中r+1 到 j 之間的元素都已滿足最小堆的要求，然後加入元素r即heap[r]，調整順序，使得到的r 到 j中間的元素都滿足要求。具體操作是将r與其子節點的值進行比較，若大于其左右孩子中的較小者，則與其交換，然後進行比較其與其新的孩子。直到r不大于其孩子或到達堆底。

建堆運算CreateHeap将一個以元素序列通過向下調整建成最小堆。調整從位置為(n-2)/2取整數部分（由于堆是一個完全二叉數，對于二叉樹，有i節點的父節點為(i-1)/2取整數部分，則這裡求的是n-1節點的父節點，也就是自底向上的第一個分支節點）的元素開始，然後重複調用AdjustDown操作，知道下标為0的元素調整完成，則建堆結束。

每執行一次AdjustDown的時間為O(log2 n)。建堆的時間複雜度為O(n)。