1
//大顶堆数据结构
2
#ifndef MAXHEAP_H
3
#define MAXHEAP_H
4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
5
template<class T>
6
class MaxHeap
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
public:
9
10
MaxHeap(T a[], int size,int maxsize=50);
11
MaxHeap(int maxsize=50);
12
virtual ~MaxHeap();
13
void Initialize(T arrays[],int size,int array_size);//用数组对堆重新进行初始化
14
MaxHeap<T>& Insert( T value);
15
MaxHeap<T>& DeleteMax(T& value );
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool IsEmpty()
{return CurrentSize==0?true:false;};
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int Size()
{return CurrentSize;}
18
void Init(T a[]);
19![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
20
private:
21
void ModifyUp(int start);
22
void ModifyDown(int start,int end);
23![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
24
private:
25
T *Data;
26
int MaxSize;
27
int CurrentSize;
28![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
29
};
30![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
31![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
32
template<class T>
33
MaxHeap<T>::MaxHeap(T a[], int size,int maxsize)
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
35
Data=a;
36
CurrentSize=size;
37
MaxSize=maxsize;
38
for( int i=CurrentSize/2;i>=1;i--)
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
40
ModifyDown(i,CurrentSize);
41![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
42
}
43![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
44
}
45![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
46
//-----------------------------------------------------------------------
47
template<class T>
48
void MaxHeap<T>::Initialize(T arrays[],int size,int array_size)
49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
50
if(Data)
51
delete[] Data;
52![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
53
Data=arrays;
54![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
55
CurrentSize=size;
56
MaxSize=array_size;
57![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
58
for(int i=CurrentSize/2;i>=1;i--)
59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
60
ModifyDown(i,CurrentSize);
61
}
62
}
63![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
64
//-------------------------------------------------------------------------
65
template<class T>
66
MaxHeap<T>::MaxHeap(int maxsize)
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
68
//0号单元不用舍弃,数据从一号单元填入
69
MaxSize=maxsize;
70
Data=new T[MaxSize+1];
71
CurrentSize=0;
72
}
73![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
74
//-------------------------------------------------------------------------
75
template<class T>
76
MaxHeap<T>::~MaxHeap()
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
78
79
delete[] Data;
80
81
}
82![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
83
//-------------------------------------------------------------------------
84
template<class T>
85
MaxHeap<T>& MaxHeap<T>::Insert(T value)
86![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
87
if(CurrentSize==MaxSize)
88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
89
cout<<"错误:堆空间已满."<<endl;
90
throw exception("堆空间已满");
91![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
92
}
93![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
94
Data[++CurrentSize]=value;
95
ModifyUp(CurrentSize);//重新调整堆
96
return *this;
97
}
98
99
//-------------------------------------------------------------------------
100
template<class T>
101
MaxHeap<T>& MaxHeap<T>::DeleteMax( T& value )
102![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
103![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
104
if(CurrentSize==0)
105![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif)
{
106
cout<<"错误:堆空."<<endl;
107
throw exception("堆空");
108![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
109
}
110
value=Data[1];
111![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
112
Data[1]=Data[CurrentSize--];
113![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
114
ModifyDown(1,CurrentSize);//重新调整堆
115
return *this;
116
}
117![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
118![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
119
//-------------------------------------------------------------------------
120
template<class T>
121
void MaxHeap<T>::ModifyUp(int start)
122![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
123
int i=start;
124
T x=Data[i];
125
//当未到达根结点并且start所指节点值大于其父节点时进行移动
126
while(i!=1&&x>Data[i/2])
127![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
128
Data[i]=Data[i/2];//将父节点下移
129
i/=2;//i指针上移
130
}
131
Data[i]=x;
132
return ;
133
}
134![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
135
//----------------------------------------------------------------
136
template<class T>
137
void MaxHeap<T>::ModifyDown(int start,int end)
138![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
139
T x=Data[start];
140![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
141
int c=2*start;
142
while(c<=end)
143![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
144
if(c<end&&Data[c]<Data[c+1]) c++;
145
if(x>Data[c]) break;
146
else
147![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
148
149
Data[c/2]=Data[c];//将孩子上移
150
c*=2;
151
}//if
152
}//while
153
Data[c/2]=x;
154
}
155
#endif
posted on 2008-09-17 19:49
杨彬彬 阅读(1368)
评论(0) 编辑 收藏 引用 所属分类:
数据结构