1
#include<iostream>
2#include<queue>
3#include<algorithm>
4using namespace std;
5
6
7template<class T>
8class ltnode
{
9
friend leftist<T>;
10public:
11 ltnode(const T& e,int sh=0)
12
{data=e;s=sh;left=right=NULL;}
13private:
14 int s;
15 T data;
16 ltnode<T>*left,*right;
17
};
18
19template<class T>
20class leftist{
21public:
22 leftist(){root==NULL;}
23 ~leftist(){free(root);}
24 T top(){ if(root==NULL);return root->data;}//
25 leftist<T>& push(const T&x);
26 leftist<T> & pop(T& x);
27 leftist<T> &concat(leftist<T>& x);
28 {concat(root,x.root);x.root=NULL;return *this;}
29 void init(T a[],int n);
30private:
31 void free(ltnode<T> *t);
32 void concat(ltnode<T>* &x,ltnode<T>*y);
33 ltnode<T>* root;
34};
35
36
37template<class T>
38void leftist<T>::free(ltnode<T> *t)
39{
40 if(t){ free(t->left );free(t->right );delete t;}
41}
42
43
44template<class T>
45void leftist<T>::concat(ltnode<T>*& x,ltnode<T>* y)
46{
47 if(y==NULL) return ;
48 if(x==NULL) x=y;return ;
49 if(x->data > y->data)swap(x,y);// min heap
50 //if( x->data < y->data)swap(x,y);//max heap
51 concat(x->right ,y);
52 if(x->left ==NULL){
53 x->left =x->right ;x->right =NULL;x->s=1;
54
}
55 else{
56 if( x->left->s < x->right ->s )swap(x->left ,x->right );
57 x->s =x->right ->x +1;
58 }
59}
60
61
62template<class T>
63leftist<T>& leftist<T>::push(const T &x)
64{
65 ltnode<T>* p=new ltnode<T>(x,1);
66 concat(root,p);
67 return *this;
68}
69
70
71template<class T>
72leftist<T>& leftist<T>::pop(T &x)
73{
74 if(root==NULL);
75 x=root->data ;
76 ltnode<T> *L=root->left ;
77 ltnode<T>* R=root->right ;
78 delete root;root=L;concat(root,R);
79 return *this;
80}
81
82
83template<class T>
84void leftist<T>::init(T a[], int n)
85{
86 queue<ltnode<T>*> Que;
87 free(root);
88 for(int i=0;i<n;i++){
89 ltnode<T> *p=new ltnode<T>(a[i],1);
90 Que.push (p);
91 }
92 ltnode<T> *b,*c;
93 for(int i=0;i<n-1;i++){
94 b=Que.front ();Que.pop ();
95 if(Que.empty )break;
96 c=Que.front ();Que.pop ();
97 concat(b,c);
98 Que.push (b);
99 }
100 if(n)root=b;
101}
102
103posted on 2009-07-12 08:53
iyixiang 阅读(213)
评论(0) 编辑 收藏 引用 所属分类:
acm