题解 P3377 【【模板】左偏树（可并堆）】

Paring Heap很好用啊，感觉比二叉堆还好写？ PS:因为不需要decrease key，无需维护father，否则可能有些繁琐 核心操作就是merge： ```cpp struct T_{int c;T_ *l,*r;}; // 权值；左儿子右兄弟 T_ *merge_(T_ *a, T_ *b) // 合并堆a和b，返回新根 { if(!a) return b; if(!b) return a; if(a->c > b->c) swap(a, b); // 小根堆。本题应写为先权值后编号比较 return b->r = a->l, a->l = b, a; } T_ *merges_(T_ *c) // （辅助）合并节点c和他的兄弟们 { if(!c || !c->r) return c; T_ *a = c->r, *b = a->r; c->r = a->r = NULL; return merge_(merge_(c, a), merges_(b)); // Paring！ } ``` 取最小直接访问根即可。 pop操作直接用merges\_(root->l)合并根的所有儿子，返回的就是新根