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

Paring Heap很好用啊，感觉比二叉堆还好写？

PS:因为不需要decrease key，无需维护father，否则可能有些繁琐

核心操作就是merge：

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)合并根的所有儿子，返回的就是新根