电影采集网站流量,微信朋友圈的广告怎么投放,合肥住房和城乡建设局,网页设计流程25算法流程#xff1a;
与⽗结点的权值作⽐较#xff0c;如果⽐它⼤#xff0c;就与⽗亲交换#xff1b; 交换完之后#xff0c;重复 1 操作#xff0c;直到⽐⽗亲⼩#xff0c;或者换到根节点的位置 这里为什么插入85完后合法#xff1f;
我们插入一个85#xff0c;…算法流程
与⽗结点的权值作⽐较如果⽐它⼤就与⽗亲交换 交换完之后重复 1 操作直到⽐⽗亲⼩或者换到根节点的位置 这里为什么插入85完后合法
我们插入一个85当85还没来的时候此时的堆是一个合法的大堆所有的节点都大于等于子树中所有节点85到来的时候我会拿它和它的父节点作比较如果它小于父结点比如3那就不用调整因为当前节点小于父节点也肯定小于父节点的父结点因为这是一个堆结构只要他小于父结点他肯定小于沿着这个节点向上的所有节点因此在3到来的时候它还是合法的但是当85到来的时候85的值大于22因此我会让较大的值往上转移转移完之后下面的堆就合法了85是大于22的因为22大于左子树数所以我把较大的值挪下来之后85肯定大于下面两颗子树里面所有的节点因此85转移下来之后下面的小树就合法了 但是上面的我们还不确定所以我们要继续拿85和上面的点做比较当我们发现85比39还大的时候就继续转移转移完之后下面的子树依旧是合法的因为39没转移之前是大于它的左子树和右子树里面所有的点所以当我把39转移到下面的时候他依旧是大于20和22这两个点的把39转移到下面的子树是不受影响的但是当我把85转移到上面的红圈中的子树就合法了原因就是刚刚85是比39大的85转移到上面之后85肯定是大于刚刚左子树里面所有的节点以及刚刚右子树里面所有的节点因为39放在这里就合法那我把85放在这里也是合法的因此当我把85转移到上面的时候整颗子树就变得合法了每次向上转移他都会让一颗小子树合法继续向上转移又会让一颗小子树合法此时我们发现85比99小左边的子树就合法了右边的子树本身就是合法的因为85到来的时候并不会影响右子树85向上调整的时候他会让一个小子树再让一颗小子树变得合法因此整个指数就变得合法了所以这里为什么合法就是一个简单比大小的过程一直让大的元素向上再向上上到不能再上的时候整个数就合法了这就是堆的第一个核心操作向上调整算法如果是小堆的话就让小元素向上走 向上调整算法时间复杂度
最坏情况下节点会从最后一层开始转移上一层再转移上一层所以他向上转移的次数跟树的高度是一样的在我们学习完全二叉树性质的时候当整棵树节点个数为N的话它的树的高度是loh以2为底N 1的对数时间复杂度就是OlogN
代码实现
const int N 1e6 10;int n;
int heap[N];//向上调整算法
void up(int child) //每次和父亲做比较
{int parent child / 2;//父节点存在且当前结点值大于父节点的权值while (parent 1 heap[child] heap[parent]){swap(heap[child], heap[parent]);child parent;parent child / 2;}
}
这个向上调整算法是为建堆服务的对我们建完堆之后再来测试
