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

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

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

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

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 const int Q = 111111;
10 template<class T>
11 struct PriQ {
12     T q[Q];
13     int sz;
14     void clear() { sz = 0;}
15     void up(int k) {
16         while (k > 1) {
17             if (q[k] < q[k >> 1]) swap(q[k >> 1], q[k]);
18             else return ;
19             k >>= 1;
20         }
21     }
22     void push(T x) {
23         q[++sz] = x;
24         up(sz);
25     }
26     void down(int k) {
27         while ((k << 1) <= sz) {
28             if ((k << 1) == sz || q[k << 1] < q[k << 1 | 1]) {
29                 if (q[k << 1] < q[k]) swap(q[k], q[k << 1]);
30                 else return ;
31                 k = k << 1;
32             } else {
33                 if (q[k << 1 | 1] < q[k]) swap(q[k], q[k << 1 | 1]);
34                 else return ;
35                 k = k << 1 | 1;
36             }
37         }
38     }
39     void pop() {
40         q[1] = q[sz];
41         sz--;
42         down(1);
43     }
44     T top() { return q[1];}
45     int size() { return sz;}
46 } ;
47 PriQ<int> pq;

View Code

左偏堆将尽快更新~

UPD：

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 template<class T>
 9 struct Node {
10     int d;
11     T dt;
12     Node *l, *r;
13     Node() { l = r = NULL;}
14     Node(T dt) : dt(dt), d(0) { l = r = NULL;}
15 } ;
16 
17 template<class T>
18 Node<T> *merge(Node<T> *a, Node<T> *b) {
19     if (!a) return b;
20     if (!b) return a;
21     if (a->dt < b->dt) return merge(b, a);
22     a->r = merge(a->r, b);
23     a->d = a->r ? a->r->d + 1 : 0;
24     return a;
25 }
26 
27 template<class T>
28 Node<T> *popTop(Node<T> *x) { return merge(x->l, x->r);}
29 
30 template<class T>
31 struct Leftist {
32     Node<T> *rt;
33     void clear() { rt = NULL;}
34     T top() { return rt->dt;}
35     void push(T dt) { rt = merge(rt, new Node<T>(dt));}
36     void pop() { rt = popTop(rt);}
37 } ;
38 
39 Leftist<int> pq;
40 
41 int main() {
42     pq.clear();
43     pq.push(10);
44     pq.push(20);
45     pq.push(15);
46     pq.push(13);
47     cout << pq.top() << endl;
48     pq.pop();
49     cout << pq.top() << endl;
50     pq.pop();
51     cout << pq.top() << endl;
52     pq.pop();
53     cout << pq.top() << endl;
54     return 0;
55 }

View Code

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

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

——written by Lyon

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

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