堆(heap)是打算机科学中一类分外的数据构造的统称，常日是一个可以被看做一棵树的数组工具。
堆{k1,k2,ki,…,kn} (ki <= k2i,ki <= k2i+1)|(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
关于堆：
完备二叉树
说到堆排序，就不能不提完备二叉树，这些基本观点在网上到处都是，我摘了个最大略的。。
完备二叉树：除末了一层外，每一层上的节点数均达到最大值；在末了一层上只短缺右边的多少结点。
我自己总结认为，正是由于有下面两个特点，
只许可末了一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上涌现（存储办法的规则性）；
若i>1，tree的双亲为tree[i p 2]（其父子结点值的规律性）；
才使得其进行排序非常方便。
堆排序
堆排序求升序用大顶堆，求降序用小顶堆。
本例用求降序的小顶堆来解析。
堆排序步骤如下：
1、我们将数据（49、38、65、97、76、13、27、50）建立一个数组$arr；
2、用数组$arr建立一个小顶堆（紧张步骤，会在代码注释里阐明，下图是用一个数组建立小顶堆的过程）；
3、将堆的根（最小的元素）与末了一个叶子交流，并将堆长度减一，跳到第二步；
4、重复2-3步，直到堆中只有一个结点，排序完成。
堆排序的PHP实现
//由于是数组,下标从0开始,以是,下标为n根结点的左子结点为2n+1,右子结点为2n+2;//初始化值,建立初始堆$arr=array(49,38,65,97,76,13,27,50);$arrSize=count($arr);//将第一次排序抽出来，由于末了一次排序不须要再交流值了。buildHeap($arr,$arrSize);for($i=$arrSize-1;$i>0;$i--){swap($arr,$i,0);$arrSize--;buildHeap($arr,$arrSize); }//用数组建立最小堆function buildHeap(&$arr,$arrSize){//打算出最开始的下标$index,如图,为数字"97"所在位置,比较每一个子树的父结点和子结点,将最小值存入父结点中//从$index处对一个树进行循环比较,形成最小堆for($index=intval($arrSize/2)-1; $index>=0; $index--){//如果有左节点,将其下标存进最小值$minif($index2+1<$arrSize){$min=$index2+1;//如果有右子结点,比较旁边结点的大小,如果右子结点更小,将其结点的下标记录进最小值$minif($index2+2<$arrSize){if($arr[$index2+2]<$arr[$min]){$min=$index2+2;}}//将子结点中较小的和父结点比较,若子结点较小,与父结点交流位置,同时更新较小if($arr[$min]<$arr[$index]){swap($arr,$min,$index);} }}}//此函数用来交流下数组$arr中下标为$one和$another的数据function swap(&$arr,$one,$another){$tmp=$arr[$one];$arr[$one]=$arr[$another];$arr[$another]=$tmp;}
下面是排序的终极结果：
堆用来进行全排序，韶光繁芜度是O(nlogn)
而快排用来全排序，均匀韶光繁芜度也是O(nlogn)
但堆排序可以用来求 TopK 时，堆的韶光繁芜度为O(Klog2(n)，由于它只须要进行 K 轮排序即可。
