广州市海珠区建设局网站,重庆seo网络推广平台,wordpress上传算流量吗,深圳华强北是干什么的关于堆不做过多介绍
堆就是儿子的值一定不小于父亲的值并且树的节点都是按照从上到下#xff0c;从左到右紧凑排列的树。
#xff08;本文为二叉堆#xff09;
具体实现并不需要指针二叉树#xff0c;用数组储存并且利用公式找到父子即可。
父#xff1a;(i-1)/2
子:…关于堆不做过多介绍
堆就是儿子的值一定不小于父亲的值并且树的节点都是按照从上到下从左到右紧凑排列的树。
本文为二叉堆
具体实现并不需要指针二叉树用数组储存并且利用公式找到父子即可。
父(i-1)/2
子:i*21,i*22
插入首先把新数字放到堆的末尾也就是右下角然后查看父的数值需要交换就交换重复上述操作直到不需交换
删除把堆的第一个节点赋值为最后一个节点的值然后删除最后一个节点不断向下交换。
两个儿子严格来说要选择数值较小的那一个
时间复杂度和深度成正比所以n个节点是O(logN)
int heap[MAX_N],sz0;
//定义数组和记录个数的变量
插入代码
void push(int x)
{//节点编号int isz;while(i0){int p(i-1)/2;//父if(heap[p]x)break;//直到大小顺序正确跳出循环heap[i]heap[p];//把父节点放下来ip;}heap[i]x;//最后把自己放上去}
弹出
int pop()
{int retheap[0];//保存好值最后返回int xheap[--sz];while(i*21sz){int ai*21;//左孩子int bi*22;//右孩子if(bsz heap[b]heap[a])ab;//找最小if(heap[a]x)break;//直到不需要交换就退出heap[i]heap[a];//把儿子放上来ia;}head[i]x;//下沉到正确位置return ret;//返回
}
