堆和优先队列

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. }

复制代码

用堆来实现优先队列，利用了堆可以用数组存储的特性

1. #include <iostream>
   
2. #include <cstring>
   
3. #include <random>
   
4. 
   
5. #define DEFAULT_CAPACITY 128
   
6. 
   
7. typedef struct _task{
   
8.     int priority;
   
9. 
   
10. }Task;
    
11. typedef Task DataType;
    
12. 
    
13. typedef struct _PriorityQueue {
    
14.     DataType* data;
    
15.     int size;
    
16.     int capacity;
    
17. }PriorityQueue;
    
18. 
    
19. bool init(PriorityQueue &pq, DataType *original, int size);
    
20. bool push(PriorityQueue &pq, DataType value);
    
21. bool pop(PriorityQueue &pq, DataType &value);
    
22. bool isEmpty(PriorityQueue &pq);
    
23. bool isFull(PriorityQueue &pq);
    
24. void destroy(PriorityQueue &pq);
    
25. 
    
26. static void build(PriorityQueue &pq);
    
27. static void adjustDown(PriorityQueue &pq, int index);
    
28. static void adjustUp(PriorityQueue &pq, int index);
    
29. 
    
30. bool init(PriorityQueue &pq, DataType *original, int size) {
    
31.     if (!original || size <= 0) {
    
32.         return false;
    
33.     }
    
34.     pq.capacity = size > DEFAULT_CAPACITY ? size : DEFAULT_CAPACITY;
    
35.     pq.data = new DataType[pq.capacity];
    
36.     // // 第一种初始化方式
    
37.     // memcpy(pq.data, original, size * sizeof(DataType));
    
38.     // pq.size = size;
    
39.     // build(pq);
    
40. 
    
41.     // 第二种初始化方式
    
42.     pq.size = 0;
    
43.     for (int i = 0; i < size; i++) {
    
44.         push(pq, original[i]);
    
45.     }
    
46.     return true;
    
47. }
    
48. 
    
49. static void build(PriorityQueue &pq) {
    
50.     for (int i = pq.size / 2 - 1; i >= 0; i--) {
    
51.         adjustDown(pq, i);
    
52.     }
    
53. }
    
54. 
    
55. static void adjustDown(PriorityQueue &pq, int index) {
    
56.     DataType cur = pq.data[index];
    
57.     int parent = index;
    
58.     int child;
    
59.    //从当前的节点开始，向下调整子节点及子节点的子节点使数组满足堆的特性
    
60.     while (parent * 2 + 1 < pq.size) {
    
61.         child = parent * 2 + 1;
    
62.         if (child + 1 < pq.size && pq.data[child].priority < pq.data[child + 1].priority) {
    
63.             child++;
    
64.         }
    
65.         if (pq.data[child].priority > cur.priority) {
    
66.             pq.data[parent] = pq.data[child];  // 子节点上移
    
67.             parent = child;
    
68.         } else {
    
69.             break;
    
70.         }
    
71.     }
    
72.     pq.data[parent] = cur;
    
73. }
    
74. 
    
75. bool push(PriorityQueue &pq, DataType value) {
    
76.     if (isFull(pq)) {
    
77.         return false;
    
78.     }
    
79.     pq.data[pq.size++] = value;
    
80.     adjustUp(pq, pq.size - 1);
    
81.     return true;
    
82. }
    
83. 
    
84. bool isFull(PriorityQueue &pq) {
    
85.     return pq.size == pq.capacity;
    
86. }
    
87. 
    
88. bool isEmpty(PriorityQueue &pq) {
    
89.     return pq.size == 0;
    
90. }
    
91. 
    
92. static void adjustUp(PriorityQueue &pq, int index) {
    
93.     DataType cur = pq.data[index];
    
94.     int child, parent;
    
95.     for (child = index; child > 0; child = parent) {
    
96.         parent = (child - 1) / 2;
    
97.         if (pq.data[parent].priority < cur.priority) {
    
98.             pq.data[child] = pq.data[parent];
    
99.             pq.data[parent] = cur;
    
100.         } else {
     
101.             break;
     
102.         }
     
103.     }
     
104. }
     
105. 
     
106. bool pop(PriorityQueue &pq, DataType &value) {
     
107.     if (isEmpty(pq)) {
     
108.         return false;
     
109.     }
     
110.     value = pq.data[0];
     
111.     pq.data[0] = pq.data[--pq.size];
     
112.     adjustDown(pq, 0);
     
113.     return true;
     
114. }
     
115. 
     
116. void destroy(PriorityQueue &pq) {
     
117.     delete[] pq.data;
     
118.     pq.data = nullptr;
     
119.     pq.size = pq.capacity = 0;
     
120. }
     
121. 
     
122. int main()
     
123. {
     
124.     std::mt19937 gen(time(0)); // random device
     
125.     std::uniform_int_distribution<int> dis(0, 9);
     
126.     PriorityQueue pq;
     
127.     Task tasks[7];
     
128.     for (int i = 0; i < 7; i++) {
     
129.         tasks[i].priority = dis(gen);
     
130.     }
     
131. 
     
132.     if (!init(pq, tasks, sizeof(tasks) / sizeof(Task))) {
     
133.         std::cerr << "init failed" << std::endl;
     
134.         return -1;
     
135.     }
     
136.     std::cout << "Tasks priority:" <<std::endl;
     
137.     for (int i = 0; i < pq.size; i++){
     
138.         std::cout << tasks[i].priority << " ";
     
139.     }
     
140.     std::cout << std::endl;
     
141.     std::cout << "Priority queue:" << std::endl;
     
142.     for (int i = 0; i < pq.size; i++){
     
143.         std::cout << pq.data[i].priority << " ";
     
144.     }
     
145.     std::cout << std::endl;
     
146. 
     
147.     push(pq, (Task){100});
     
148.     std::cout << "Priority queue after push:" << std::endl;
     
149.     for (int i = 0; i < pq.size; i++){
     
150.         std::cout << pq.data[i].priority << " ";
     
151.     }
     
152.     std::cout << std::endl;
     
153.     return 0;
     
154. }
     

复制代码