优先队列和堆的实现
···堆的逻辑结构是一种二叉树，而物理结构是一维数组，它拥有以下特点：
1*、儿子的值一定不小于父亲的值。
2、树的节点是按照从上到下，从左到右的顺序紧凑排列的。
在插入操作时，先把数值放到堆的末尾，然后检查他的位置是否合适（他的值是否大于父节点的值），不合适则往上交换。
在输出操作时，先出0位置的元素，然后把末尾的元素放到0位置，然后检查0位置是否合适，不合适则向下交换，注意：是与子节点中值更小的那个交换。
这是我自己写的push（）和pop（）的实现：
#include <iostream> #include <cstdio> #define MAX_N 100005// using namespace std; int sz=0;// int heap[MAX_N]; void push(int x){ int i=sz++; heap[i]=x; int p=(i-1)/2; while(heap[p]>heap[i]){ heap[p]^=heap[i]; heap[i]^=heap[p]; heap[p]^=heap[i]; i=p; p=(i-1)/2; } } int pop(){ int ans=heap[0]; heap[0]=heap[--sz]; int i=0; int l=i*2+1,r=i*2+2; int minn=heap[l]<heap[r]?l:r ; while(heap[i]>heap[minn]&&r<sz){ heap[i]^=heap[minn]; heap[minn]^=heap[i]; heap[i]^=heap[minn]; i=minn; l=i*2+1;r=i*2+2; minn=heap[l]<heap[r]?l:r ; } return ans; } int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++){ int t; scanf("%d",&t); push(t); } while(sz){ printf("%d ",pop()); } return 0; }
···堆实际上正好解决“优先队列”的问题，优先队列有以下两个特点：
1、插入一个数值。
2、每次取出最小的数值。
···一般情况下优先队列并不用自己实现，在c++中stl里的priority_queue就是，不过这个每次取出的是最大值，下面是一个简单例子：
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 using namespace std; 5 6 int main() 7 { 8 priority_queue<int> pque; 9 pque.push(3); 10 pque.push(5); 11 pque.push(1); 12 13 while(!pque.empty()){ 14 printf("%d\n",pque.top()); 15 pque.pop(); 16 } 17 return 0; 18 }
另外如果想要从小到大的输出，有个简单的小技巧，对于整数可以这样处理：
#include <iostream> #include <cstdio> #include <queue> using namespace std; int main() { priority_queue<int> pque; pque.push(100-3); pque.push(100-5); pque.push(100-1); while(!pque.empty()){ printf("%d\n",100-pque.top()); pque.pop(); } return 0; }
