• 常数较二叉堆小。
• 采用 new、delete 分配内存，不喜勿喷。
• 支持任意类型（需定义 operator< 或传入比较器）（需要默认构造函数）

如有错请指正！谢谢！

template<typename T, typename Comp = less<T>> class pairing_heap {public:typedef Comp comparer;pairing_heap() : _r(nullptr) { }~pairing_heap() { while(!empty()) pop(); }void push(T o){_Node *n = new _Node;n->v = o, n->son = n->sib = nullptr;_r = _merge(_r, n);}T top(){return _r ? _r->v : T();}void pop(){_Node *nr = _multi_merge(_r->son);if(_r) delete _r;_r = nr;}bool empty(){return !_r;}void join(pairing_heap<T, Comp> &p){_r = _merge(_r, p._r);p._r = nullptr;}private:struct _Node{T v;_Node *son, *sib;} *_r;comparer _C;_Node *_merge(_Node *a1, _Node *a2){if(!a1 || !a2) return a1 ? a1 : a2;if(_C(a1->v, a2->v)) swap(a1, a2);_Node *s = a1->son;if(!s) a1->son = a2;else{a2->sib = s->sib;s->sib = a2;}return a1;}_Node *_multi_merge(_Node *a){_Node *b, *c;if(!a) return nullptr;if(!a->sib) return a;b = a->sib, a->sib = nullptr;if(!b->sib) return _merge(a, b);c = b->sib, b->sib = nullptr;return _merge(_merge(a, b), _multi_merge(c));} };

转载于:https://www.cnblogs.com/js2xxx/p/9437465.html

总结

以上是生活随笔为你收集整理的手打配对堆模板（支持push, pop, top, join）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。