题解 P3378 【【模板】堆】

这是很基础的一道模板题，如不能掌握，可读《啊哈！算法》《编程珠玑》等书，将会有详细的解释。 纯C代码，愿用C的伙伴们能看得懂。 ```cpp #include <stdio.h> #define MAXN 900 //有效的数组大小 int heap[MAXN]; int heapn=1; //浪费了heap[0],以便计算 void siftup(int); void siftdown(int); int main(void){ int n; int i; int tempa,tempb; scanf("%d",&n); for (i=0;i<n;i++){ scanf("%d\n",&tempa); switch (tempa){ case 1: scanf("%d",&tempb); heap[heapn++]=tempb; //heapn始终表示最后一个元素的索引加1的值 siftup(heapn); //把刚才插入的元素往上调 break; case 2: printf("%d\n",heap[1]); //输出堆顶元素，注意要换行 break; case 3: heap[1]=heap[--heapn]; //把最后一个元素放到堆顶，并把原来存放最后一个元素的位置视为可用 siftdown(heapn); //把刚才交换的元素往下调 break; default: break; } } return 0; } void siftup(int n){ int i=n-1; //为刚才插入的元素的位置 int t; //交换元素用 while (i>1){ //如果该元素不在堆顶，就要继续调整 if (heap[i]<heap[i>>1]){ //如果该元素比它的父节点小，就需要调整。i>>1相当于i/2 t=heap[i>>1]; heap[i>>1]=heap[i]; heap[i]=t; i>>=1; //跟踪该元素的位置 } else { break; //否则调整完毕 } } } void siftdown(int n){ int i=1; //为刚才交换的元素的位置 int index_min; //用于存储两个子节点中最小的那一个的位置 int t; //交换元素用 while ((i<<1)<n){ //当这个元素仍有子节点时进行调整。i<<1相当于i*2 index_min=i<<1; //暂时设为左子节点的位置 if (index_min+1<n && heap[index_min+1]<heap[index_min]){ //如果右节点比左节点更小，就更新为右节点的位置 index_min++; } if (heap[i]<=heap[index_min]){ //如果该节点比它的两个子节点都要小，就调整完毕 break; } t=heap[index_min]; // 否则交换该节点和它最小的一个子节点 heap[index_min]=heap[i]; heap[i]=t; i=index_min; //更新该节点的位置 } } ```