编程练习——堆heap

因为vs2005中c++的Heap构造有些问题，所以才重写了heap类。

不知道vs2008中这个是不是个bug。

1. /*createdbychicochen
2. *date2008/10/25
3. */
4. template<classT,classCmp>
5. classHeap
6. {
7. private:
8. vector<T>heap;
9. voidShiftDown(intindex)
10. {
11. while(!IsLeaf(index))
12. {
13. intl=Lchild(index);
14. intr=Rchild(index);
15. if(r!=-1)
16. {
17. if(Cmp::Up(heap[r],heap[l]))
18. {
19. //puttheupnodetotheleft
20. swap(heap[l],heap[r]);
21. }
22. }
23. if(Cmp::Up(heap[l],heap[index]))
24. {
25. //uptheleftchild
26. swap(heap[l],heap[index]);
27. index=l;
28. }
29. else
30. {
31. break;
32. }
33. }
35. }
36. voidShiftUp(intindex)
37. {
38. intparent=-1;
39. while(index!=0)
40. {
41. parent=Parent(index);
42. if(Cmp::Up(heap[index],heap[parent]))
43. {
44. swap(heap[index],heap[parent]);
45. index=parent;
46. }
47. else
48. {
49. break;
50. }
51. }
53. }
54. voidReHeapAll()
55. {
56. for(inti=Parent(heap.size()-1);i>=0;i--)
57. {
58. ShiftDown(i);
59. }
60. }
61. voidReHeapOne(intindex)
62. //setonepriorandre-positiontheindexnode
63. {
64. Tdata=heap[index];
65. ShiftDown(index);
66. if(Cmp::Eq(data,heap[index]))
67. {
68. ShiftUp(index);
69. }
70. }
71. intParent(intindex)
72. //parentnodeoftheindexnode
73. {
74. return(index-1)/2;
75. }
76. intLchild(intindex)
77. //Leftchildoftheindexnode
78. {
79. if(!IsLeaf(index))
80. returnindex*2+1;
81. return-1;
82. }
83. intRchild(intindex)
84. //Rightchildoftheindexnode
85. {
86. if(!IsLeaf(index))
87. {
88. intr=index*2+2;
89. if(r<heap.size())
90. returnr;
91. }
92. return-1;
93. }
95. intIsLeaf(intindex)
96. {
97. assert(index<heap.size());
98. if(heap.size()==1)
99. returntrue;
100. intlastNode=Parent(heap.size()-1);
101. returnlastNode<index;
102. }
104. intFindData(T&data)
105. {
106. intlen=heap.size();
107. for(inti=0;i<len;i++)
108. {
109. if(Cmp::Eq(data,heap[i]))
110. {
111. returni;
112. }
113. }
114. return-1;//cannotfindthedata
115. }
117. voidprintTree(intindex,intcount)
118. {
119. if(index<heap.size()&&index>=0)
120. {
122. printTree(Rchild(index),count+4);
123. for(inti=0;i<count;i++)
124. {
125. cout<<"";
126. }
127. cout<<heap[index]<<endl;
128. printTree(Lchild(index),count+4);
129. }
130. }
131. public:
132. Heap()
133. {
134. heap=vector<T>();
135. }
136. ~Heap()
137. {
138. //heapdestroyed
139. }
140. boolIsEmpty()
141. {
142. returnheap.size()==0;
143. }
147. voidInsert(T&data)
148. {
149. heap.push_back(data);
150. ShiftUp(heap.size()-1);
151. }
152. voidDelete(intindex)
153. {
154. intlast=heap.size()-1;
155. if(index>=0&&index<=last)
156. {
158. swap(heap[index],heap[last]);
159. heap.pop_back();
160. ReHeapOne(index);
161. }
162. }
163. voidDelete(T&data)
164. {
165. intindex=FindData(data);
166. if(index!=-1)
167. Delete(index);
168. }
171. voidRemoveTop()
172. {
174. if(!IsEmpty()&&heap.size()>1)
175. {
176. swap(heap[0],heap[heap.size()-1]);
177. heap.pop_back();
178. ShiftDown(0);
179. }
180. elseif(heap.size()==1)
181. {
182. heap.pop_back();
183. }
185. }
186. T&Top()
187. {
188. returnheap[0];
189. }
191. voidPrint()
192. {
193. printTree(0,1);
194. }
198. };