核心操作是sift_up,和sift_down,其他所有操作都是建立在这两个核心操作的基础上的,事实上所有的堆结构都可以使用这两个操作。
const int maxsize = 10001; int size = 0; int min_heap[maxsize];/*0号单元不使用,因为如果使用0单元,则k/2无法找到其父结点*/ void sift_up(int k)//从第k个位置开始,计算能否上升 { int tmp = min_heap[k]; for(; k>1;k=k>>1 )/*如果小于其父亲,退出循环时k位置的值始终已经被保存了副本*/ { if(tmp < min_heap[k>>1]) min_heap[k] = min_heap[k>>1]; else break; } min_heap[k] = tmp; } void sift_down(int k)//从第k个位置开始,计算能否下降 { int tmp = min_heap[k]; for(k=k<<1; k<=size; k=k<<1)/*每次优先跳转到左孩子,当前k的父结点k>>1位置的元素始终被保存了副本*/ { if(k+1<=size && min_heap[k+1] < min_heap[k])/*如果右孩子更小*/ ++k; if(tmp > min_heap[k]) min_heap[k>>1] = min_heap[k]; else break; } min_heap[k>>1] = tmp; } /*增加*/ void push(int x)/*插入元素x*/ { min_heap[++size] = x; sift_up(size); } /*删除*/ /****** 按关键字的值来pop的操作在关键一定无重复的时候可以有, 但一旦有重复关键字,那么pop操作是很难正确实现的 *******/ void pop(int k=1)/*弹出位于k位置的元素,1是默认堆顶*/ { min_heap[k] = min_heap[size--];/*堆尾元素替换k位置*/ sift_up(k); sift_down(k); } int getTop() { int top = min_heap[1]; pop(1); return top; } /*修改*/ void update(int k,int x)/*将第k位置的元素的关键字更新为x*/ { min_heap[k] = x; sift_up(k); sift_down(k); }