堆的实现

 1. 堆的结构

堆就是像下图这样的二叉树。

堆最重要的性质就是儿子的值- -定 不小于父亲的值。除此之外,树的节点是按从上倒下、从左到右的顺序紧凑排列的。

如上图所示，在向堆中插入数值时，首先在堆的末尾插人该数值，然后不断向上提升直到没有大小颠倒为止。

如上图所示，从堆中删除最小值时,首先把堆的最后- - 个节点的数值复制到根节点上,并且删除最后-一个节点。然后不断向下交换直到没有大小颠倒为止。在向下交换的过程中，如果有2个儿子，那么选择数值较小的儿子(如果儿子比自己小的话)进行交换。

2.堆的操作的复杂度

堆的两种操作所花的时间都和树的深度成正比。因此，如果一共有n个元素， 那么每个操作可以在O(logn)的时间内完成。

3.堆的实现

下面我们来看一. 下堆的实现的例子。我们不使用指针来表示二叉树，而是如下图所示，给每个节点赋予-一个编号，并用数组来存储。此时，儿子的编号就满足如下性质。

■左儿子的编号是自己的编号x2+1

■右儿子的编号是自己的编号x2+2

4.代码实现 

#include<iostream>
#include<vector>
using namespace std;
vector<int>heap(100000);
int sz=0;
void push(int x) {
	int i=sz++; 
	while(i>0) {
		int p=(i-1)/2;
		if(heap[p]<=x)
			break;
		heap[i]=heap[p];
		i=p;
	}
	heap[i]=x;
}
int pop() {
	int ret=heap[0];
	int x=heap[--sz];
	int i=0;
	while(i*2+1<sz) {
		int a=2*i+1,b=2*i+2;
		if(b<sz&&heap[a]>heap[b])
			a=b;
		if(heap[a]>=x)
			break;
		heap[i]=heap[a];
		i=a;
	}
	heap[i]=x;
	return ret;
}
int main() {
	int n;
	cin>>n;
	for(int i=0; i<n; ++i) {

		int x;
		cin>>x;
		push(x);
	}
	for(int i=0; i<n; ++i) {
		cout<<pop()<<" ";
	}
}