堆是一种树结构
堆分为2种，即大根堆和小根堆。
大根堆的定义是，在树中除了根节点，任意一个节点的值都小于它的父节点
类似得，小根堆的定义是，在树中除了根节点，任意一个节点的值都大于它的父节点
值得注意的是，一个堆任一子树也是堆（非常重要的性质）
一般来说使用的是二叉堆。

堆的主要用途是排序，最有名的算法就是 堆排序（heapsort）。
如果不考虑 桶排序（BINSORT） 这种犯规级别的排序，可以认为是仅劣于快速排序（qsort）的排序算法。
不过比起快速排序，堆排序的优势在于，空间需求更小，而且不会像快速排序一样——存在时间复杂度退化到O（N^2）的可能性
不过比起快速排序最大的劣势在于，堆排序的编程复杂度过大。

堆的存储一般使用数组存储，一般使堆为完全二叉树（即除了叶子节点，所有节点都有2个子节点），其中 len 表示堆中节点数目
其中 对于非叶子节点 T(i) 来说，其左子节点 为 T(i*2)，右子节点为 T(i*2+1)
堆的主要操作有 建堆（build）、添加节点（add 不常见） 、删除跟节点（delete)、维护堆(分为 hold 与 add_hold)
注意！！！ 以下讨论都以小根堆为例

hold & add_hold
维护是整个堆操作的核心，维护就是把经过其他操作后的堆（此时堆的结构已经破坏）调整成堆
维护 有2种
hold 为自上而下调整，使用较多，在 build 和 delete 中使
add_hold 为自上而下调整，一般只在add 中使用
这是因为堆添加节点一般只在最后，而删除一般只删除根节点

hold 的思想如下（以delete为例)
假设已经有了一个堆。删掉根节点（方法是，将根节点和最后一个节点 T(len)的交换，len<- len-1），这时除了根节点外，它的任一子树
都是堆（“值得注意的是，一个堆任一子树也是堆”）
首先调整根节点和它的子节点，假设 T(2)<T(3)<T(1) 这时候交换 T(2)、T(1), 于是根节点和它的子节点成为堆，因为T(3)没有变化，所
以根节点的右子树不用调整。 对于左子树来说，除了它的根节点——T(2)，其余部分也满足堆，所以可以重复以上过程。
待调整到 叶子节点，就完成了维护

hold 伪代码 (tree[] 表示存储堆的数组）
hold(p)
l<- p*2
r<- l+1
if l>len {exit} (如果是叶子节点就退出)
if r>len
{
if tree[l]<tree[p] {swap(l,p) hold(l)} (swap(a,b) 即交换 T(a) , T(b))
}
if (tree[l]<tree[p]) or (tree[r]<tree[p])
{
if tree[l]<tree[r] {swap(l,p) hold(l)} else {swap(r,p) hold(r)}
}

add_hold 自下而上和hold实质上是类似的，就给出伪代码
add_hold(x);
if x=1 {exit} (如果是根节点就退出)
p<- [x/2] ([X] 高斯记号，值为 整数N ,N满足 N<=X 且 N+1>X 。 当X>=0 时 相当于取整数部分)
if mod(x,2)=1 {l<-x r<-x+1} else {l<-x-1 r<-x} (这里我在程序中用了其他写法，其实是等价的)
if r>len
{
if tree[l]<tree[p] {swap(l,p) add_hold(p)}
}
if (tree[l]<tree[p]) or (tree[r]<tree[p])
{
if tree[l]<tree[r] {swap(l,p)} else {swap(r,p)}
add_hold(p)
}

delete 的思想已经给出,伪代码入下
delete
swap(1,len)
len<- len-1
hold(1)
add 伪代码如下（因为不常用就不详细讲了，可以结合伪代码研究下）
add(x)
len<- len+1
tree[len]<- x
if len>1 {add_hold(len)}

假设有数组 tree[len] 里面有 len 个数   
建堆伪代码
for i= len ~ 1 hold(i)
解释一下：
在调整某个节点时，它的子节点肯定已经调整过了，所以除它外，它的任一子树都是一个堆。
这就和delete时的情况完全一样，所以可以用hold把这个节点调整好。
然后依次调整，最后调整完根节点，就完成了建堆

下面给出 heapsort 的伪代码
for i= 1 ~ len
{
print tree[1]
delete;
}
由堆的性质我们可以知道，小根堆的根节点一定是最小值（大根堆反之）。那么每次输出根节点，并删掉根节点，一共 len 次 最后就完成
了排序

总的来说，
hold add_hold 时间复杂度都是 O(log2n)
因此， build 的时间复杂度为 O(nlog2n) ，heapsort 的时间复杂度也为 O(nlog2n)
所以总体时间复杂度也为 O(nlog2n)
优于冒泡排序的 O(n^2)

话说heap的左边的括号是全角的，右边的是半角的，看起来怪怪的

程序果然要通过I贴吧来发...贴吧吃回车太恐怖了
115下载稍等...

高贵的排序，不过数据量比较小的时候用冒泡也不错