本文共 862 字，大约阅读时间需要 2 分钟。

堆是一种简单高效的数据结构，在很多常用算法的优化上大显身手。

堆的常数很小，同样的数据，用堆来排序和快排的速度几乎相等，但是平衡树的速度会慢很多，Splay慢了两倍多。。

简单的学习一下堆，把模板发出来与大家分享

CODE（小根堆，排序）：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 200010#define INF 0x7f7f7f7fusing namespace std;struct SmallHeap{	int num[MAX];	int last;	int Top() {		return num[1];	}	void Insert(int x) {		num[++last] = x;		int now = last;		while(num[now] < num[now >> 1] && now > 1)			swap(num[now],num[now >> 1]),now >>= 1;	}	void Pop() {		num[1] = num[last--];		int now = 2;		while(now <= last) {			if(num[now] > num[now + 1])	++now;			if(num[now] < num[now >> 1])	swap(num[now],num[now >> 1]),now <<= 1;			else	break;		}	}}heap;int cnt;int main(){	cin >> cnt;	for(int x,i = 1;i <= cnt; ++i) {		scanf("%d",&x);		heap.Insert(x);	}	for(int i = 1;i <= cnt; ++i) {		printf("%d\n",heap.Top());		heap.Pop();	}	return 0;}
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/39051111 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！