1. 不得不說說二叉樹
要了解堆首先得了解一下二叉樹，在計算機科學中，二叉樹是每個節(jié)點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。
二叉樹的每個結點至多只有二棵子樹（不存在度大于 2 的結點），二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第 i 層至多有 2i - 1 個結點；深度為 k 的二叉樹至多有 2k - 1 個結點；對任何一棵二叉樹 T，如果其終端結點數(shù)為 n0，度為 2 的結點數(shù)為 n2，則n0 = n2 + 1。
樹和二叉樹的三個主要差別：
樹的結點個數(shù)至少為 1，而二叉樹的結點個數(shù)可以為 0
樹中結點的最大度數(shù)沒有限制，而二叉樹結點的最大度數(shù)為 2
樹的結點無左、右之分，而二叉樹的結點有左、右之分
二叉樹又分為完全二叉樹（complete binary tree）和滿二叉樹（full binary tree）
滿二叉樹：一棵深度為 k，且有 2k - 1 個節(jié)點稱之為滿二叉樹

（深度為 3 的滿二叉樹 full binary tree）
完全二叉樹：深度為 k，有 n 個節(jié)點的二叉樹，當且僅當其每一個節(jié)點都與深度為 k 的滿二叉樹中序號為 1 至 n 的節(jié)點對應時，稱之為完全二叉樹

（深度為 3 的完全二叉樹 complete binary tree）
2. 什么是堆？
堆（二叉堆）可以視為一棵完全的二叉樹，完全二叉樹的一個“優(yōu)秀”的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數(shù)組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個結點對應數(shù)組中的一個元素。
如下圖，是一個堆和數(shù)組的相互關系

（堆和數(shù)組的相互關系）
對于給定的某個結點的下標 i，可以很容易的計算出這個結點的父結點、孩子結點的下標：
Parent(i) = floor(i/2)，i 的父節(jié)點下標
Left(i) = 2i，i 的左子節(jié)點下標
Right(i) = 2i + 1，i 的右子節(jié)點下標

二叉堆一般分為兩種：最大堆和最小堆。
最大堆：
最大堆中的最大元素值出現(xiàn)在根結點（堆頂）
堆中每個父節(jié)點的元素值都大于等于其孩子結點（如果存在）

（最大堆）
最小堆：
最小堆中的最小元素值出現(xiàn)在根結點（堆頂）
堆中每個父節(jié)點的元素值都小于等于其孩子結點（如果存在）

（最小堆）
3. 堆排序原理
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個過程持續(xù)到剩余數(shù)只有一個時結束。在堆中定義以下幾種操作：
最大堆調整（Max-Heapify）：將堆的末端子節(jié)點作調整，使得子節(jié)點永遠小于父節(jié)點
創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
堆排序（Heap-Sort）：移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調整的遞歸運算
繼續(xù)進行下面的討論前，需要注意的一個問題是：數(shù)組都是 Zero-Based，這就意味著我們的堆數(shù)據(jù)結構模型要發(fā)生改變

（Zero-Based）
相應的，幾個計算公式也要作出相應調整：
Parent(i) = floor((i-1)/2)，i 的父節(jié)點下標
Left(i) = 2i + 1，i 的左子節(jié)點下標
Right(i) = 2(i + 1)，i 的右子節(jié)點下標
最大堆調整（MAX