二叉堆&&左偏堆 代码实现

　　今天打算学习左偏堆，可是想起来自己二叉堆都没有看懂，于是就跑去回顾二叉堆了。发现以前看不懂的二叉堆，今天看起来特简单，随手就写好了一个堆了。

　　简单的说一下我对二叉堆操作的理解。我不从底层函数说上去，相反，我打算从实现来解释底层函数的构造，以大堆为例。

　　其实操作都很简单，对于push函数，因为堆是一棵严格的完全二叉树，所以我们直接在队列的尾端插入新增加的元素。然后就将这个元素不停的跟他的父节点进行比较，如果这个元素更大就跟父节点交换，否则就退出上推更新这个操作。对于pop的操作也是差不多的，我们可以将出堆的元素的位置用最底的元素替换。然后就是将这个替换上堆顶的元素下推。对于当前这个元素的位置，如果左儿子比右儿子大，就用左儿子跟当前元素比较，如果左儿子比较大，就把左儿子交换上去。反之亦然。

通过简单测试的二叉堆代码如下：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int Q = ;

 template<class T>

 struct PriQ {

     T q[Q];

     int sz;

     void clear() { sz = ;}

     void up(int k) {

         while (k > ) {

             if (q[k] < q[k >> ]) swap(q[k >> ], q[k]);

             else return ;

             k >>= ;

         }

     }

     void push(T x) {

         q[++sz] = x;

         up(sz);

     }

     void down(int k) {

         while ((k << ) <= sz) {

             if ((k << ) == sz || q[k << ] < q[k <<  | ]) {

                 if (q[k << ] < q[k]) swap(q[k], q[k << ]);

                 else return ;

                 k = k << ;

             } else {

                 if (q[k <<  | ] < q[k]) swap(q[k], q[k <<  | ]);

                 else return ;

                 k = k <<  | ;

             }

         }

     }

     void pop() {

         q[] = q[sz];

         sz--;

         down();

     }

     T top() { return q[];}

     int size() { return sz;}

 } ;

 PriQ<int> pq;

左偏堆将尽快更新~

UPD：

通过小数据测试的左偏堆代码实现（大堆）：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 template<class T>

 struct Node {

     int d;

     T dt;

     Node *l, *r;

     Node() { l = r = NULL;}

     Node(T dt) : dt(dt), d() { l = r = NULL;}

 } ;

 template<class T>

 Node<T> *merge(Node<T> *a, Node<T> *b) {

     if (!a) return b;

     if (!b) return a;

     if (a->dt < b->dt) return merge(b, a);

     a->r = merge(a->r, b);

     a->d = a->r ? a->r->d +  : ;

     return a;

 }

 template<class T>

 Node<T> *popTop(Node<T> *x) { return merge(x->l, x->r);}

 template<class T>

 struct Leftist {

     Node<T> *rt;

     void clear() { rt = NULL;}

     T top() { return rt->dt;}

     void push(T dt) { rt = merge(rt, new Node<T>(dt));}

     void pop() { rt = popTop(rt);}

 } ;

 Leftist<int> pq;

 int main() {

     pq.clear();

     pq.push();

     pq.push();

     pq.push();

     pq.push();

     cout << pq.top() << endl;

     pq.pop();

     cout << pq.top() << endl;

     pq.pop();

     cout << pq.top() << endl;

     pq.pop();

     cout << pq.top() << endl;

     return ;

 }

　　目前只支持基本的合并以及删除最大值的操作。

http://jidayangfei.blog.163.com/blog/static/1349366082010107114825861/

——written by Lyon