今天，我们来谈一谈一个很常用的数据结构---堆。
堆（Heap），也叫优先队列（Priority Queue）。
是一种完全二叉树，树根是整个树最大或最小的元素。（对应的就是最大堆和最小堆，后文讨论最大堆）
先来看一个最大堆的例子吧
1.JPG
可以看到56是整个堆最大的元素，接着对于19来说，19又是以它为根的堆的最大的元素，40也是。
由于是完全二叉树，所以用数组来存储堆，比用链表来存储堆要方便许多。
哦，对了，好像还没说什么是完全二叉树吧，完全二叉树就是二叉树是满的，如果不是完全二叉树，这棵树可能长成这个样子。。
2.JPG
所以，完全二叉树是有特点的，如果存放为数组a的话，我们从数组的下标1开始存放我们的数组，那么56对应的下标是1，19对应的下标是2，40对应3....可以看到，若一个节点的下标是i，那么它的左儿子的下标就是2i，右儿子的下标就是2i+1。
同理，如果一个儿子（不管是左儿子还是右儿子）的下标是i，那么他的父节点的下标就是i/2；
正因为如此，用数组存储堆就显得极其容易了。
下面我们定义堆的结构(操作集还未加入)。
class Heap{
protected:
int *data;
int size;
int Capcity;
Heap(int size):size(0),Capcity(size) {
data = new int[size + 1];
data[0]=MaxData;
}
}
Heap（n）的构造函数，给我一个n，我就创造一个容量为n的堆，动态分配n+1个空间给数组，同时数组的下标0设置成哨兵。（后文会讲什么是哨兵）
对于堆来说，我们主要的操作是插入和删除，真正的难点在于，我们要保证我们插入和删除了之后，仍是一个最大堆或最小堆。
以最大堆为例，如果我们在堆中插入了一个新元素（如图3），
图3
那么实质是我们在堆中数组的7号位置存放我们的新元素，如果插入的元素比44小，那还是堆，但一旦插入的元素大于44，甚至大于58，那就不是堆了，我们的解决办法是什么？
交换元素的位置。
怎么个交换法？我们插入的元素要跟父节点的元素比，大的话就交换，交换好了就继续再跟父节点的父节点比，如果还大就接着交换。
所以，如果我们插入了60，那么60的下标是7，父节点是7/2=3，60和44比，发现大，就交换，44换到下标为7的位置，而3的位置放着60，接着3/2=1，60去和58比，比58大，接着交换，就这样一直循环下去。
最后如果换到了下标为1（也就是我们现在的情况），下标为1的父节点就会是哨兵了，所以，只要我们设置哨兵的值比任何值都大，我们的循环就一定会停止。
所以插入的代码如下。
void push(int x){
if(full()){//判断堆是否还没满
cout<<"full push"<<endl;
return;
}
int i=++size;
for(;x>data[i/2];i/=2)
data[i]=data[i/2];
data[i]=x;
}
现在，让我们看一看删除是怎么回事。
删除其实就是弹出根节点（最大的元素）。
图3
还是图3，首先我们弹出了58，然而解决方法还是交换~
首先我们把最后一个元素，下标为6的31提拔到根节点处，
图4
然后去跟两个儿子比，如果比较大的那个儿子（也就是44）的元素值大于父节点（也就是现在的31），就 交换 ！！
然后就循环直到没有儿子为止，或者不用交换为止！
所以，
删除的代码如下：
int pop(){
if(empty()){//判断是否空
cout<<"empty pop"<<endl;
return MaxData;
}
int x=data[1];
int temp=data[size--];
if(size==0)return x;
int Parent=1;
int child;
while(2*Parent<=size){//Parent有儿子
child=Parent*2;
if(child+1<=size&&data[child]<data[child+1]){//指向child中较大的一个
child++;
};
if(temp>=data[child])break;
data[Parent]=data[child];
Parent=child;
}
data[Parent]=temp;
return x;
}
最后，让我们来谈一谈堆排序，什么是堆排序呢？
堆排序就是比如说我告诉你我要你插入n个数，然后你就先把n个数一一填到堆的数组中，注意，不是插入，填完以后并不是堆，而是就像普通的数组一样，都填完了，再进行整体的排序，排成堆。
我们的做法是这样的，对于数组，从第一个有儿子的下标开始，进行排堆操作，一直排到下标为1为止，什么是排堆操作呢？
就是把以该节点为根节点，建成一个堆，代码和删除的代码很像！！
（把该节点与两儿子中的大的比较，然后如果儿子大就交换，否则就停止！）几乎可以把删除的后半部分代码复制成排堆操作的代码。
下面给出代码：
protected:
void Sorted(int i){//所谓的堆排序
int temp=data[i];
int child;
while(2*i<=size){
child=2*i;
if(child+1<=size&&data[child]<data[child+1])
child++;
if(temp>=data[child])break;
data[i]=data[child];
i=child;
}
data[i]=temp;
}
public:
void build(int n){
if(n>Capcity){
cout<<"n is greater than Capcity"<<endl;
return;
}
int x;
for(int i=1;i<=n;i++){
cin>>x;
data[i]=x;
}
int i=size=n;
i/=2;//第一个有儿子的结点
for(;i>=1;i--){
Sorted(i);
}
}
值得注意的是：堆排序的时间复杂度居然是o（n）！！
网友评论