|
|
Posted on 2010-05-02 20:39 Current 閱讀(1514) 評論(0) 編輯 收藏 引用 所屬分類: Wild Magic 引擎解析
最大堆和最小堆是二叉堆的兩種形式。
- 最大堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最大者的堆。
- 最小堆：根結(jié)點(diǎn)的鍵值是所有堆結(jié)點(diǎn)鍵值中最小者的堆。
而最大-最小堆集結(jié)了最大堆和最小堆的優(yōu)點(diǎn)，這也是其名字的由來。 最大-最小堆是最大層和最小層交替出現(xiàn)的二叉樹，即最大層結(jié)點(diǎn)的兒子屬于最小層，最小層結(jié)點(diǎn)的兒子屬于最大層。 以最大（小）層結(jié)n點(diǎn)為根結(jié)點(diǎn)的子樹保有最大（小）堆性質(zhì)：根結(jié)點(diǎn)的鍵值為該子樹結(jié)點(diǎn)鍵值中最大（小）項(xiàng)。
最大堆：  最小堆：  最小堆實(shí)現(xiàn)：
1 #ifndef _TMINHEAP_HPP_
2#define _TMINHEAP_HPP_
3
4#include "System.hpp"
5
6namespace PX2
7   {
8  /**//// 最小堆
9 /**//*
10 * 應(yīng)用二叉樹實(shí)現(xiàn)最小堆
11 */
12 template <typename Generator, typename Real> class TMinHeap;
13
14 template <typename Generator, typename Real>
15 class TMinHeapRecord
16 {
17 public:
18 TMinHeapRecord ();
19 ~TMinHeapRecord ();
20
21 Generator GetGenerator () const;
22 Real GetValue () const;
23
24 private:
25 friend class TMinHeap<Generator, Real>;
26
27 Generator m_tGenerator;
28 Real m_fValue;
29 int m_iIndex;
30 };
31
32 template <typename Generator, typename Real>
33 class TMinHeap
34 {
35 TMinHeap ( int iMaxQuantity, int iGrowBy );
36 ~TMinHeap ();
37
38 int GetMaxQuantity () const;
39 int GetGrowBy () const;
40 int GetQuantity () const;
41 const TMinHeapRecord<Generator,Real>* GetRecord ( int i ) const;
42
43 const TMinHeapRecord<Generator,Real>* Insert (Generator tGenerator,
44 Real fValue);
45
46 void Remove (Generator& rtGenerator, Real& rfValue);
47
48 void Update (const TMinHeapRecord<Generator,Real>* pkConstRecord,
49 Real fValue);
50
51 bool IsValid (int iStart, int iFinal);
52 bool IsValid ();
53 void Print (const char* acFilename);
54
55 private:
56 int m_iMaxQuantity, m_iGrowBy, m_iQuantity;
57 TMinHeapRecord<Generator,Real>* m_akRecords;
58
59 TMinHeapRecord<Generator,Real>** m_apkRecords;
60 };
61
62#include "TMinHeap.inl"
63 }
64#endif//_TMINHEAP_HPP_
1//----------------------------------------------------------------------------
2template <typename Generator, typename Real>
3TMinHeapRecord<Generator,Real> ::TMinHeapRecord ()
4{
5}
6//----------------------------------------------------------------------------
7template <typename Generator, typename Real>
8TMinHeapRecord<Generator,Real> ::~TMinHeapRecord ()
9{
10}
11//----------------------------------------------------------------------------
12template <typename Generator, typename Real>
13Generator TMinHeapRecord<Generator,Real> ::GetGenerator () const
14{
15 return m_tGenerator;
16}
17//----------------------------------------------------------------------------
18template <typename Generator, typename Real>
19Real TMinHeapRecord<Generator,Real> ::GetValue () const
20{
21 return m_fValue;
22}
23//----------------------------------------------------------------------------
24//-------------------------------------------------------------------------------
25template <typename Generator, typename Real>
26TMinHeap<Generator, Real> ::TMinHeap( int iMaxQuantity, int iGrowBy )
27{
28 assert( iMaxQuantity > 0 && iGrowBy > 0);
29 m_iMaxQuantity = iMaxQuantity;
30 m_iGrowBy = iGrowBy;
31 m_iQuantity = 0;
32 m_akRecords = NEW TMinHeapRecord<Generator, Real>[m_iMaxQuantity];
33 m_apkRecords = NEW TMinHeapRecord<Generator, Real>*[m_iMaxQuantity];
34
35 for (int i = 0; i < m_iMaxQuantity; ++i)
36 {
37 m_apkRecords[i] = &m_akRecords[i];
38 m_apkRecords[i]->m_iIndex = i;
39 }
40}
41//-------------------------------------------------------------------------------
42template <typename Generator, typename Real>
43TMinHeap<Generator, Real> ::~TMinHeap()
44{
45 DELETE [] m_akRecords;
46 DELETE [] m_apkRecords;
47}
48//-------------------------------------------------------------------------------
49template <typename Generator, typename Real>
50int TMinHeap<Generator, Real> ::GetMaxQuantity() const
51{
52 return m_iMaxQuantity;
53}
54//-------------------------------------------------------------------------------
55template <typename Generator, typename Real>
56int TMinHeap<Generator, Real> ::GetGrowBy() const
57{
58 return m_iGrowBy;
59}
60//-------------------------------------------------------------------------------
61template <typename Generator, typename Real>
62int TMinHeap<Generator, Real> ::GetQuantity()
63{
64 return m_iQuantity;
65}
66//-------------------------------------------------------------------------------
67template <typename Generator, typename Real>
68const TMinHeapRecord<Generator, Real>* TMinHeap<Generator, Real>
69::GetRecord ( int i ) const
70{
71 if ( 0 <= i && i < m_iQuantity )
72 {
73 return m_apkRecords[i];
74 }
75
76 return 0;
77}
78//-------------------------------------------------------------------------------
79template <typename Generator, typename Real>
80const TMinHeapRecord<Generator,Real>* TMinHeap<Generator,Real>
81::Insert ( Generator tGenerator, Real fValue )
82{
83 if ( m_iQuantity == m_iMaxQuantity )
84 {
85 int iNewQuantity = m_iMaxQuantity + m_iGrowBy;
86
87 TMinHeapRecord<Generator,Real>* akNewRecords =
88 NEW TMinHeapRecord<Generator,Real>[iNewQuantity];
89
90 TMinHeapRecord<Generator,Real>** apkNewRecords =
91 NEW TMinHeapRecord<Generator,Real>*[iNewQuantity];
92
93 size_t uiSize = m_iMaxQuantity*sizeof(TMinHeapRecord<Generator,Real>);
94 memcpy(akNewRecords, m_akRecords, uiSize);
95
96 int i;
97 for (i = 0; i < m_iMaxQuantity; i++)
98 {
99 int iByteOffset = (int)(m_apkRecords[i] - m_akRecords);
100 apkNewRecords[i] = (TMinHeapRecord<Generator,Real>*)
101 ( ((char*)akNewRecords) + iByteOffset);
102 apkNewRecords[i]->m_iIndex = i;
103 }
104
105 for (i = m_iMaxQuantity; i < iNewQuantity; i++)
106 {
107 apkNewRecords[i] = &akNewRecords[i];
108 apkNewRecords[i]->m_iIndex = i;
109 }
110
111 DELETE[] m_akRecords;
112 DELETE[] m_apkRecords;
113 m_iMaxQuantity = iNewQuantity;
114 m_akRecords = akNewRecords;
115 m_apkRecords = apkNewRecords;
116 }
117
118 int iChild = m_iQuantity++;
119 TMinHeapRecord<Generator, Real>* pkRecord = m_apkRecords[iChild];
120 pkRecord->m_tGenerator = tGenerator;
121 pkRecord.m_fValue = fValue;
122
123 while (iChild > 0)
124 {
125 int iParent = ( iChild - 1) / 2;
126 if (m_apkRecords[iParent].m_fValue <= fValue)
127 {
128 break;
129 }
130
131 m_apkRecords[iChild] = m_apkRecords[iParent];
132 m_apkRecords[iChild].m_iIndex = iChild;
133
134 m_apkRecords[iParent] = pkRecord;
135 m_apkRecords[iParent].m_iIndex = iParent;
136
137 iChild = iParent;
138 }
139
140 return m_apkRecords[iChild];
141}
142//-------------------------------------------------------------------------------
143template <typename Generator, typename Real>
144void TMinHeap<Generator, Real> ::Remove(Generator& rtGenerator, Real& rfValue)
145{
146 TMinHeapRecord<Generator, Real>* pkRoot = m_apkRecords[0];
147 rtGenerator = pkRoot->m_tGenerator;
148 rfValue = pkRoot->m_fValue;
149
150 int iLast = --m_iQuantity;
151 TMinHeapRecord<Generator, Real>* pkRecord = m_apkRecords[iLast];
152 int iParent = 0, iChild = 1;
153 while (iChild <= iLast )
154 {
155 if (iChild < iLast )
156 {
157 int iChildP1 = iChild + 1;
158 if (m_apkRecords[iChild]->m_fValue >
159 m_apkRecords[iChildP1]->m_fValue)
160 {
161 iChild = iChildP1;
162 }
163 }
164
165 if (m_apkRecords[iChild]->m_fValue >= pkRecord->m_fValue)
166 {
167 break;
168 }
169
170 m_apkRecords[iParent] = m_apkRecords[iChild];
171 m_apkRecords[iParent]->m_iIndex = iParent;
172
173 iParent = iChild;
174 iChild = 2*iChild + 1;
175 }
176 m_apkRecords[iParent] = pkRecord;
177 m_apkRecords[iParent]->m_iIndex = iParent;
178
179 m_apkRecords[iLast] = pkRoot;
180 m_apkRecords[iLast]->m_iIndex = iLast;
181}
182//-------------------------------------------------------------------------------
183template <typename Generator, typename Real>
184void TMinHeap<Generator, Real> ::Update(
185const TMinHeapRecord<Generator,Real>* pkConstRecord, Real fValue)
186
187{
188 TMinHeapRecord<Generator, Real>* pkRecord =
189 (TMinHeapRecord<Generator, Real>*) pkConstRecord;
190
191 int iParent, iChild, iChildp1, iMaxChild;
192
193 if (fValue > pkRecord->m_fValue )
194 {
195 pkRecord->m_fValue = fValue;
196
197 iParent = pkRecord->m_iIndex;
198 iChild = 2* iParent + 1;
199 while( iChild < m_iQuantity)
200 {
201 if (iChild < m_iQuantity -1)
202 {
203 iChildp1 = iChild + 1;
204 if (m_apkRecords[iChild]->m_fValue <=
205 m_apkRecords[iChildp1]->m_fValue )
206 {
207 iMaxChild = iChild;
208 }
209 else
210 {
211 iMaxChild = iChildp1;
212 }
213 }
214 else
215 {
216 iMaxChild = iChild;
217 }
218
219 if (m_apkRecords[iMaxChild]->m_fValue >= fValue )
220 {
221 break;
222 }
223
224 m_apkRecords[iParent] = m_apkRecords[iMaxChild];
225 m_apkRecords[iParent]->m_iIndex = iParent;
226
227 m_apkRecords[iMaxChild] = pkRecord;
228 m_apkRecords[iMaxChild]->m_iIndex = iMaxChild;
229
230 iParent = iMaxChild;
231
232 iChild = 2* iParent + 1;
233 }
234 }
235 else if (fValue < pkRecord->m_fValue)
236 {
237 pkRecord->m_fValue = fValue;
238
239 iChild = pkRecord->m_iIndex;
240
241 while( iChild > 0)
242 {
243 iParent = (iChild -1) /2;
244 if (m_apkRecords[iParent]->m_fValue <= fValue)
245 {
246 break;
247 }
248
249 m_apkRecords[iChild] = m_apkRecords[iParent];
250 m_apkRecords[iChild]->m_iIndex = iChild;
251
252 m_apkRecords[iParent] = pkRecord;
253 m_apkRecords[iParent]->m_iIndex = iParent;
254
255 iChild = iParent;
256 }
257 }
258}
259//-------------------------------------------------------------------------------
260template <typename Generator, typename Real>
261bool TMinHeap<Generator, Real> ::IsValid( int iStart, int iFinal)
262{
263 for ( int iChild = iStart; iChild <= iFinal; ++iChild)
264 {
265 int iParent = (iChild - 1)/2;
266 if (iParent > iStart)
267 {
268 if (m_apkRecords[iParent]->m_fValue >
269 m_apkRecords[iChild]->m_fValue )
270 {
271 return false;
272 }
273
274 if (m_apkRecords[iParent]->m_iIndex != iParent)
275 {
276 return false;
277 }
278 }
279 }
280
281 return true;
282}
283//-------------------------------------------------------------------------------
284template <typename Generator, typename Real>
285bool TMinHeap<Generator,Real> ::IsValid ()
286{
287 return IsValid(0, m_iQuantity-1);
288}
289//-------------------------------------------------------------------------------
290template <typename Generator, typename Real>
291void TMinHeap<Generator,Real> ::Print (const char* acFilename)
292{
293 std::ofstream kOStr(acFilename);
294 for (int i = 0; i < m_iQuantity; i++)
295 {
296 TMinHeapRecord<Generator,Real>* pkRecord = m_apkRecords[i];
297 kOStr << pkRecord->m_iIndex << ": gen = " << pkRecord->m_tGenerator
298 << " , val = " << pkRecord->m_fValue << std::endl;
299 }
300 kOStr.close();
301}
302//----------------------------------------------------------------------------
303
304// end
|