定义一个堆:
int heap[maxn] ; //存储堆
int len; //堆中元素个数
将一个数插入堆:
在堆中插入元素x
首先将元素x放到堆中的最后一个位置(即最底层最右边的位置),然后不断地把x往上调整,直到x调不动为止(即大于它现在的父亲,或者x处于根结点)
void insert(int x) //将x放进堆
{
heap[++len]=x; //把当前数放进堆尾
int i=len; //i为要调整的数在heap[]中的位置
while (i>1&&heap[i]<heap[i/2])
//还没调到堆头,因为是小根堆,要满足儿子大于父亲,如果儿子小于父亲说明需要调整
{
swap(heap[i],heap[i/2]);//儿子和父亲交换
i/=2; //交换后要调整的数的位置也改变了
}
}
在堆中删除位置为k的元素
首先把位置k的元素和最后一个位置的元素交换,然后删去最后一个位置,这样k上的元素就被删除了
接着把位置k上的新元素不断下调,直到满足堆的性质
void del(int k) //删除堆中位置为k的元素
{
int i=k,j; //i:父亲 j:儿子
heap[k]=heap[len];
len--; //将堆顶赋值为堆尾的数,再删除堆尾,调整堆顶的位置(往下移动)
while (i*2<=len)//把还没调到堆尾
{
if (i*2==len||heap[i*2]<heap[i*2+1]) j=i*2; else j=i*2+1;
//小根堆要满足父亲小于儿子,左儿子小于右儿子,j就是找左右儿子较小的那一个,与父亲进行交换
if (heap[j]<heap[i]) swap(heap[j],heap[i]),i=j;
//如果儿子小于父亲,可以交换,更新父亲的位置
else return; //否则此时的二叉堆满足堆的性质,可以返回
}
}