POJ3481(待完善版本，请看注释)

#include <iostream> using namespace std;//根据需求调整大小 #define SIZE 10typedef struct Node{int K;int P; }Node; Node big[SIZE]; Node small[SIZE]; int big_size=1; int small_size=1;void swap(Node x, Node y) {Node tmp;tmp.K = x.K;tmp.P = x.P;x.K = y.K;x.P = y.P;y.K = tmp.K;y.P = tmp.P; } void big_fixDown(Node heap[], int pos, int size){int x = pos;if(x > size) return;//exit// 选出最大的int l = 2 * x;int r = l + 1;int maxPos = x;if(l <= size && heap[maxPos].P < heap[l].P) maxPos = l;if(r <= size && heap[maxPos].P < heap[r].P) maxPos = r;if(maxPos != x){ //如果父节点不是最大的，进行互换，并在新的点上继续fixDown swap(heap[x], heap[maxPos]);big_fixDown(heap, maxPos, size);} } void small_fixDown(Node heap[], int pos, int size){int x = pos;if(x > size) return;//exit// 选出最大的int l = 2 * x;int r = l + 1;int maxPos = x;if(l <= size && heap[maxPos].P > heap[l].P) maxPos = l;if(r <= size && heap[maxPos].P > heap[r].P) maxPos = r;if(maxPos != x){ //如果父节点不是最大的，进行互换，并在新的点上继续fixDown swap(heap[x], heap[maxPos]);big_fixDown(heap, maxPos, size);} }void big_fixUp(Node heap[], int pos){int x = pos;int p;while(x > 1){p = x/2;if(heap[x].P > heap[p].P){swap(heap[x], heap[p]);x = p;}else return;} } void small_fixUp(Node heap[], int pos){int x = pos;int p;while(x > 1){p = x/2;if(heap[x].P < heap[p].P){swap(heap[x], heap[p]);x = p;}else return;} } void buildHeap(int heap[], int size){for(int i = size/2; i >= 1; i--){big_fixDown(heap, i, size);} }//heapSort前要先build heap void heapSort(int heap[], int size){int oriSize = size;for(int i = 0; i < oriSize - 1; i++){ //注意不要把oriSize和size混在一起//互换堆顶和最后一个元素，将堆顶元素放在数组最后面swap(heap[size], heap[1]);size--;fixDown(heap, 1, size);} } void insert(){//构建大根堆和小根堆 big_fixUp(big,big_size);small_fixUp(small,small_size); } int big_pop(){//函数里面还没有加pop大根堆对于小跟堆的影响int ret = 0;ret = big[1].K;big[1] = big[big_size-1];big[big_size-1].P = 0;//downbig_fixDown(big,1,big_size);return ret; }void small_pop(){//函数里面还没有加pop小根堆对于大跟堆的影响int ret = 0;ret = small[1].K;small[1] = small[big_size-1];small[big_size-1].P = 0;small_fixDown(small,1,small_size);return ret; } int main(){freopen("input.txt","r",stdin);int cmd;int k,p;while(scanf("%d",cmd)&&cmd!=0){switch(cmd){case 1: scanf("%d %d",&k,&p);big[big_size].K = k;big[big_size++].P = p;//指向要放入的位置small[small_size].K = k;small[small_size++].P = p;insert();break;case 2: break;case 3: break;}}return 0; }

 

转载于:https://www.cnblogs.com/linux0537/p/7523896.html

总结

以上是生活随笔为你收集整理的POJ3481(待完善版本，请看注释)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。