堆的储存:
int dui[];
int size;//储存堆的大小
堆中调整的两个基本函数
这里的堆定义为最小堆
下沉 down():如果当前数变大,就会下沉.
** 实现思路:比较左右孩子和根节点,取最小值和根节点互换值,从交换后的左/右孩子继续down()
void down(int index){
int u=index;
if(index*2<=cnt&&dui[index*2]<dui[u])u=index*2;//左孩子存在并且值小于根节点
if(index*2+1<=cnt&&dui[index*2+1]<dui[u])u=index*2+1;//右孩子存在并且值小于根节点
if(u!=index){
swap(dui[index],dui[u]);
down(u);
}
}
上浮 up():如果当前数变小,就会上浮
void up(int index){
while(index/2&&dui[index]<dui[index/2]){//无论当前节点是左孩子还是右孩子,父节点都是index/2
swap(dui[index],dui[index/2]);
index/=2;
}
}
后面的操作都基于上面两个函数