下文中以小根堆为例。
启发式合并
考虑维护多个优先队列，每次从小的合并到大的即可。
合并总复杂度 \(O(n \log^2 n)\)，太慢了。
随机堆
考虑暴力合并的过程，容易造出极端数据卡死。
那我们就在每次合并时进行随机化。
int merge(int x,int y){if(!x || !y){return x|y;}if(val[x]>val[y]){swap(x,y);}if(rand()%2){lc[x]=merge(lc[x],y);}else{rc[x]=merge(rc[x],y);}return x;
}
平均下来，单次合并时间复杂度是 \(O(\log n)\) 的。
这么简单，你为什么还要学可并堆？