• 常數(shù)較二叉堆小。
• 采用 new、delete 分配內(nèi)存，不喜勿噴。
• 支持任意類型（需定義 operator< 或傳入比較器）（需要默認(rèn)構(gòu)造函數(shù)）

如有錯(cuò)請(qǐng)指正！謝謝！

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));} };

轉(zhuǎn)載于:https://www.cnblogs.com/js2xxx/p/9437465.html

總結(jié)

以上是生活随笔為你收集整理的手打配对堆模板（支持push, pop, top, join）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。