如果在递归的时候旋转:(借用题解rk2的代码)
void insert(int &id,int v){//id依然是引用,在新建节点时可以体现
if(!id){
id = New(v);//若节点为空,则新建一个节点
return ;
}
if(v == val[id])cnt[id]++;//若节点已存在,则副本数++;
else{//要满足BST性质,小于插到左边,大于插到右边
int d = v < val[id] ? 0 : 1;//这个d是方向的意思,按照BST的性质,小于本节点则向左,大于向右
insert(ch[id][d],v);//递归实现
if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);//(参考一下图)与左节点交换右旋,与右节点交换左旋
}
pushup(id);//现在更新一下本节点的信息
}
那么旋转过程中似乎不能保证优先级的大顶堆性质吧?
因为旋转的话原子节点的孩子会变成原父节点的节点,但只有原父节点比原子节点小的时候会旋转,这时候原父节点有可能比原子节点的孩子的优先级小,就会导致最后父节点比子节点小的情况
而且这个是递归实现的,处理完当前节点以后不会把它的子节点处理,所以这个错误会一直保留下去
如果这样不能保证的话,有没有别的办法可以保证?