堆结构是一种数组对象，其定义如下：它是完全二叉树或者近似完全二叉树。经常作为优先级队列，比如二叉树优先级队列，四叉树优先级队列。
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。
k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
优先级队列是不同于先进先出队列的另一种队列。
最大优先级队列，是这样的一种队列结构，它的内部存放着一系列的元素，每个元素都对应着一个最优级，
最大优先级队列不管各元素的入队顺序，在出队时，总是对应优先级最大的元素出队。
最小优先级队列正好相反，不管入队的顺序，对应的权值最小的队列元素出队列。
优先级队列可以用二叉树来实现，比如最大元素出队列，只要在二叉树中用常数时间取出最大值就可以了。取出了最大值之后，要继续调整树的状态，使得第二大节点放入根节点。
堆排序
基本思想：对一组待排序记录的关键字，首先建立一个堆，然后输出最大（小）关键字，使得其余的关键字重新构成一个堆，得到次大（小）的元素。这样反复执行，使得记录成为一个有序序列，这个过程就称为堆排序。由此可见，堆排序主要解决两个问题：（1）如何使得一个无序的序列称为一个有序的序列；（2）如何在输出对顶元素之后，调整剩余元素使之称为一个堆。
调整堆的过程：从非终端节点开始，一直到最后节点。
//调整堆使之称为大（小）顶堆
void HeapAdjust(int *data,int s,int m)
{
int j;
int rc = data[s];
for (j = 2 * s; j < m; j *= 2) //沿着关键字较大的孩子节点向下筛选
{
if (j < m && data[j] < data[j+1])
{
++j; //j是值较大元素的下标
}
if (!(rc<data[j]))
{
break;
}
data[s] = data[j];
s = j; //rc应插入在位置s上
}
data[s] = rc; //插入
}
而建立堆只要从最后一个非叶子节点开始，向前逐步调整，这种调整的方法常称为“筛选法”。
//堆排序
void Heap_Sort(int* a,int n)
{
int i = 0;
for (i=n/2; i>0; i--) //把a建成大顶堆
{
HeapAdjust(a,i,n-1);
}
int temp; //临时变量
for (i=n-1; i>0; i--) //将当前节点和最后一个数据交换
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
HeapAdjust(a,0,i-1);
}
}
堆排序的优点：平均时间复杂度是最坏时间复杂度都是O（nlogn），效率比较高。仅仅需要一个供交换用的辅助记录大小空间。
缺点：不稳定，相同的数据元素在排序过程中可能移动位置。对于记录数较少的排序不适合。