【C++】基于数组实现的最小堆

膜法记者

初学数据结构，欢迎指正。

1. #include<iostream>
   
2. using namespace std;
   
3. 
   
4. template <typename T>
   
5. class MinHeap {
   
6. private:
   
7.         const static int MAX_SIZE = 20;
   
8.         const static int EX_SIZE = 20;
   
9.         int heapSize;
   
10.         int maxSize;
    
11.         T *heap;
    
12.         void _sort(); // 整体排序
    
13.         void _sortUp(int start); // 上滑排序
    
14. public:
    
15.         MinHeap(int size = MAX_SIZE);
    
16.         MinHeap(T arr[], int size);
    
17.         ~MinHeap();
    
18.         void insert(const T& value); // 插入新结点
    
19.         void forShow(); // 遍历数组输出，仅用于测试
    
20.         int getSize();
    
21.         int getMaxSize();
    
22.         bool getTop(T &value);
    
23.         bool remove(T &value);
    
24.         void remove();
    
25.         void makeEmpty();
    
26. };
    
27. 
    
28. template <typename T>
    
29. MinHeap<T>::MinHeap(int size) {
    
30.         heap = new T[size];
    
31.         maxSize = size;
    
32.         heapSize = 0;
    
33. }
    
34. 
    
35. template <typename T>
    
36. MinHeap<T>::MinHeap(T arr[], int size) {
    
37.         maxSize = (size > MAX_SIZE) ? size : MAX_SIZE;
    
38.         heap = new T[maxSize];
    
39.         heapSize = size;
    
40.         for (int i = 0; i < size; i++) {
    
41.                 heap[i] = arr[i];
    
42.         }
    
43.         _sort();
    
44. }
    
45. 
    
46. template <typename T>
    
47. MinHeap<T>::~MinHeap() {
    
48.         delete[] heap;
    
49. }
    
50. 
    
51. template <typename T>
    
52. void MinHeap<T>::insert(const T& value) {
    
53.         if (heapSize == maxSize) {
    
54.                 T *hn = new T[maxSize + EX_SIZE];
    
55.                 for (int i = 0; i < maxSize; i++) {
    
56.                         hn[i] = heap[i];
    
57.                 }
    
58.                 delete[] heap;
    
59.                 heap = hn;
    
60.         }
    
61.         heap[heapSize] = value;
    
62.         _SiftUp(heapSize);
    
63.         heapSize++;
    
64. }
    
65. 
    
66. template <typename T>
    
67. void MinHeap<T>::forShow() {
    
68.         for (int i = 0; i < heapSize; i++) {
    
69.                 cout << heap[i] << endl;
    
70.         }
    
71. }
    
72. 
    
73. template <typename T>
    
74. void MinHeap<T>::_sort() {
    
75.         int i, j, k;
    
76.         T temp;
    
77.         for (i = heapSize - 1; i > 0; i--) {
    
78.                 k = i;
    
79.                 j = (k - 1) / 2;
    
80.                 if (heap[k] < heap[j]) {
    
81.                         temp = heap[k];
    
82.                         heap[k] = heap[j];
    
83.                         heap[j] = temp;
    
84.                 }
    
85.                 j = (k + 1) * 2 - 1;
    
86.                 while (j <= heapSize - 1 && heap[k] > heap[j]) {
    
87.                         temp = heap[k];
    
88.                         heap[k] = heap[j];
    
89.                         heap[j] = temp;
    
90.                         k = j;
    
91.                         j = (j + 1) * 2 - 1;
    
92.                 }
    
93.         }
    
94. }
    
95. 
    
96. template <typename T>
    
97. void MinHeap<T>::_sortUp(int start) {
    
98.         int i = start;
    
99.         int j = (i - 1) / 2;
    
100.         T temp = heap[i];
     
101.         //while中不作交换，只把较大的父节点往下填
     
102.         while (i > 0) {
     
103.                 if (temp < heap[j]) {
     
104.                         heap[i] = heap[j];
     
105.                         i = j;
     
106.                         j = (i - 1) / 2;
     
107.                 }
     
108.                 else {
     
109.                         break;
     
110.                 }
     
111.         }
     
112.         //填入正确位置
     
113.         heap[i] = temp;
     
114. }
     
115. 
     
116. template <typename T>
     
117. int MinHeap<T>::getSize() {
     
118.         return heapSize;
     
119. }
     
120. 
     
121. template <typename T>
     
122. int MinHeap<T>::getMaxSize() {
     
123.         return maxSize;
     
124. }
     
125. 
     
126. template <typename T>
     
127. bool MinHeap<T>::getTop(T &value) {
     
128.         if (heapSize == 0) {
     
129.                 return false;
     
130.         }
     
131.         else {
     
132.                 value = heap[0];
     
133.                 return true;
     
134.         }
     
135. }
     
136. 
     
137. template <typename T>
     
138. bool MinHeap<T>::remove(T &value) {
     
139.         if (heapSize == 0) {
     
140.                 return false;
     
141.         }
     
142.         else {
     
143.                 value = heap[0];
     
144.                 remove();
     
145.                 return true;
     
146.         }
     
147. }
     
148. 
     
149. template <typename T>
     
150. void MinHeap<T>::remove() {
     
151.         if (heapSize == 0) {
     
152.                 return;
     
153.         }
     
154.         heapSize--;
     
155.         heap[0] = heap[heapSize];
     
156.         _sort();
     
157. }
     
158. 
     
159. template <typename T>
     
160. void MinHeap<T>::makeEmpty() {
     
161.         heapSize = 0;
     
162. }

复制代码

以下是测试代码

1. int main() {
   
2.         int a[] = {53,17,78,9,45,65,87,23};
   
3.         MinHeap<int> h(a,8);
   
4.         h.forShow();
   
5.         return 0;
   
6. }

复制代码

如果T是一个类，要求它必须重载了>、<、>=等运算符
附_sort()和_sortUp()原理图