大小根堆
2024-12-07 19:14:22
发布于：浙江
9阅读
0回复
0点赞
大小根堆
大根堆
简介: 是一种特殊的树形结构，保证根结点一定是当前树集合当中最大的元素。 (小根堆刚好相反)
每当我们插入一个新的元素的时候，我们会将其插入在当前树的最后一个结点当中。(PS: 大小根堆一定是一个完全二叉树，即最后一个结点一定是最后一层的最后一列)。
将新插入的结点与其父结点做比较，假如更大的结点作为孩子存在，那么就会跟父亲结点替换，继续跟父亲的父亲结点比较，直到父亲结点比该结点更大或者到根结点为止。
int root ; // 新加入的结点编号
int parent ; // 父结点编号
// 假设根结点的编号为1
int Tree[MAXN] ; // 保存每一个对应结点的数值
void updata(int root,int parent){ // 当我们插入结点的时候，更新树的时候
while(root!= 1 && Tree[root] > Tree[parent]){
swap(Tree[root],Tree[parent]); // 父结点的值大于子结点的值，则交换两者的值
root = parent ; // 继续跟父结点比较
parent = root/2 ; // 计算父结点的编号
}
}
假如我们要删除某个结点，那么我们就要从当前结点所处的根结点开始往下更新，每个根结点需要从两个孩子当中选择一个更符合规则的孩子作为新的根结点替代，然后继续来到替代的孩子结点，查找下一个替代的孩子。
int root ; // 要删除的结点编号
int left ; // 左孩子结点编号
int right ; // 右孩子结点编号
void deletroot(int root,int left,int right){
while(left != 0 || right != 0){
// 我们设置0为不存在该结点。
if(Tree[left] > Tree[right]){
swap(Tree[root],Tree[left]); // 左孩子结点的值更大，则将根结点与左孩子结点交换
}else{
swap(Tree[root],Tree[right]); // 右孩子结点的值更大，则将根结点与右孩子结点交换
}
root = left ; // 继续跟左孩子结点比较
left = 2*root ; // 计算左孩子结点的编号
right = 2*root+1 ; // 计算右孩子结点的编号
}
}
这里空空如也
有帮助，赞一个