当前位置：首页 > article >正文

向上调整算法（详解）c++

article 2025/1/31 18:03:15

算法流程：

与⽗结点的权值作⽐较，如果⽐它⼤，就与⽗亲交换；
交换完之后，重复 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的对数，时间复杂度就是O（logN）

代码实现：

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;
	}
}