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