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

评论