堆和优先队列

pyzyd

堆有最大堆和最小堆，

堆是完全二叉树，
要求：
1.每个父节点大于（或小于）等于其子节点，左右子节点没有大小要求
2.堆最多只能有一个单个的左子节点，不能有多个结点，不能是单个的右子节点

1.      90
   
2.     /  \
   
3.    70   80
   
4.   / \   / \
   
5. 60  20 75 50
   
6. 
   
7. 这就是一个最大堆
   
8. 
   
9. 错误示例
   
10.      1
    
11.     / \
    
12.    2   3
    
13.   /   /

复制代码

堆的代码实现

1. /*
   
2. 堆是特殊的树，
   
3. 堆是完全二叉树，
   
4. 堆中每一个节点的值都大于或等于其左右孩子节点的值，称为大顶堆（最大堆）；
   
5. 堆中每一个节点的值都小于或等于其左右孩子节点的值，称为小顶堆（最小堆）。
   
6. 堆可以用数组表示，数组中第i个元素，其左孩子为2i+1，右孩子为2i+2。
   
7. */
   
8. 
   
9. #include <cstring>
   
10. #include <iomanip>
    
11. #include <iostream>
    
12. #include <string>
    
13. #include <cmath>
    
14. 
    
15. #define DEFAULT_CAPCITY 128
    
16. 
    
17. typedef int DataType;
    
18. 
    
19. typedef struct _Heap {
    
20.     DataType *data;
    
21.     int size;
    
22.     int capacity;
    
23. } Heap;
    
24. 
    
25. bool initHeap(Heap &heap, int *original, int size);
    
26. bool insert(Heap &heap, DataType value);
    
27. static void buildHeap(Heap &heap);
    
28. static void adjustDown(Heap &heap, int index);
    
29. static void adjustUp(Heap &heap, int index);
    
30. 
    
31. 
    
32. int main() {
    
33.     Heap hp;
    
34.     int origVals[] = {1, 2, 3, 87, 93, 82, 92, 86, 95};
    
35.     if (!initHeap(hp, origVals, sizeof(origVals) / sizeof(origVals[0]))) {
    
36.         std::cerr << "init heap failed!" << std::endl;
    
37.         return -1;
    
38.     }
    
39. 
    
40.     if (typeid(1.0) == typeid(float)) {
    
41.         std::cout << "1.0 is float" << std::endl;
    
42.     } else {
    
43.         std::cout << "1.0 is double" << std::endl;
    
44.     }
    
45.     insert(hp, 100);
    
46.     return 0;
    
47. }
    
48. 
    
49. 
    
50. bool initHeap(Heap &heap, int *original, int size) {
    
51.     if (original == nullptr || size <= 0) {
    
52.         return false;
    
53.     }
    
54.     heap.capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;
    
55.     heap.data = new DataType[heap.capacity];
    
56.     if (!heap.data) {
    
57.         return false;
    
58.     }
    
59.     memcpy(heap.data, original, size * sizeof(int));
    
60.     heap.size = size;
    
61.     buildHeap(heap);
    
62.     return true;
    
63. }
    
64. 
    
65. bool insert(Heap &heap, DataType value) {
    
66.     if (heap.size == heap.capacity) {
    
67.         return false;
    
68.     }
    
69.     int index = heap.size++;
    
70.     heap.data[index] = value;
    
71.     adjustUp(heap, index);
    
72.     return true;
    
73. }
    
74. 
    
75. /*
    
76. 从最后一个非叶子结点（父节点 size / 2 - 1
    
77. 的位置）逐个往前调整所有父节点（直到根节点），
    
78. 确保每一个父节点都是一个最大堆，最终整个堆就是一个最大堆。
    
79. */
    
80. static void buildHeap(Heap &heap) {
    
81.     int i;
    
82.     for (i = heap.size / 2 - 1; i >= 0; i--) {
    
83.         adjustDown(heap, i);
    
84.     }
    
85. }
    
86. 
    
87. /*
    
88. 将当前节点和子节点调整成最大堆
    
89. */
    
90. static void adjustDown(Heap &heap, int index) {
    
91.     int cur = heap.data[index];
    
92.     int parent, child;
    
93.     for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
    
94.         child = parent * 2 + 1;
    
95.         // 比较左子节点和右子节点，取较大的那个
    
96.         if ((child + 1) < heap.size &&
    
97.             heap.data[child] < heap.data[child + 1]) {
    
98.             child++;
    
99.         }
    
100.         // 如果当前节点大于等于最大子节点，则不需要调整
     
101.         if (cur >= heap.data[child]) {
     
102.             break;
     
103.         } else {
     
104.             // 否则，将当前节点和最大子节点交换
     
105.             heap.data[parent] = heap.data[child];
     
106.             heap.data[child] = cur;
     
107.         }
     
108.     }
     
109. }
     
110. 
     
111. static void adjustUp(Heap &heap, int index) {
     
112.     if (index < 0 || index >= heap.size) {
     
113.         return;
     
114.     }
     
115.     while (index > 0) {
     
116.         int parent = (index - 1) / 2;
     
117.         if (heap.data[index] <= heap.data[parent]) {
     
118.             break;
     
119.         }
     
120. 
     
121.         // 交换当前节点与父节点
     
122.         int temp = heap.data[index];
     
123.         heap.data[index] = heap.data[parent];
     
124.         heap.data[parent] = temp;
     
125. 
     
126.         index = parent;
     
127.     }
     
128. }

复制代码