如果在递归的时候旋转:(借用题解rk2的代码)
void insert(int &id,int v){
if(!id){
id = New(v);
return ;
}
if(v == val[id])cnt[id]++;
else{
int d = v < val[id] ? 0 : 1;
insert(ch[id][d],v);
if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);
}
pushup(id);
}
那么旋转过程中似乎不能保证优先级的大顶堆性质吧?
因为旋转的话原子节点的孩子会变成原父节点的节点,但只有原父节点比原子节点小的时候会旋转,这时候原父节点有可能比原子节点的孩子的优先级小,就会导致最后父节点比子节点小的情况
而且这个是递归实现的,处理完当前节点以后不会把它的子节点处理,所以这个错误会一直保留下去
如果这样不能保证的话,有没有别的办法可以保证?