![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
1
#include<iostream>
2
#include<queue>
3
#include<algorithm>
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7
template<class T>
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class ltnode
{
9
friend leftist<T>;
10
public:
11
ltnode(const T& e,int sh=0)
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{data=e;s=sh;left=right=NULL;}
13
private:
14
int s;
15
T data;
16
ltnode<T>*left,*right;
17
};
18![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
19
template<class T>
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
class leftist
{
21
public:
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
leftist()
{root==NULL;}
23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
~leftist()
{free(root);}
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{concat(root,x.root);x.root=NULL;return *this;}
29
void init(T a[],int n);
30
private:
31
void free(ltnode<T> *t);
32
void concat(ltnode<T>* &x,ltnode<T>*y);
33
ltnode<T>* root;
34
};
35![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
36![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
37
template<class T>
38
void leftist<T>::free(ltnode<T> *t)
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(t)
{ free(t->left );free(t->right );delete t;}
41
}
42![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
43![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
44
template<class T>
45
void leftist<T>::concat(ltnode<T>*& x,ltnode<T>* y)
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(x->left ==NULL)
{
53
x->left =x->right ;x->right =NULL;x->s=1;
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
56
if( x->left->s < x->right ->s )swap(x->left ,x->right );
57
x->s =x->right ->x +1;
58
}
59
}
60![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
61![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
62
template<class T>
63
leftist<T>& leftist<T>::push(const T &x)
64![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
65
ltnode<T>* p=new ltnode<T>(x,1);
66
concat(root,p);
67
return *this;
68
}
69![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
70![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
71
template<class T>
72
leftist<T>& leftist<T>::pop(T &x)
73![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
82![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
83
template<class T>
84
void leftist<T>::init(T a[], int n)
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
86
queue<ltnode<T>*> Que;
87
free(root);
88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
103![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2009-07-12 08:53
iyixiang 阅读(207)
评论(0) 编辑 收藏 引用 所属分类:
acm