二叉堆实现优先队列（大根堆、小根堆）

大根堆

大根堆是根节点比其儿子结点值要大的二叉堆，故优先队列的队首数值是最大的。具体实现见代码：

#include<iostream> #include<cstdio> using namespace std; const int maxn = 1000; class Priority_queue //大根堆，优先队列 { public: int heap[maxn], tot; Priority_queue(); ~Priority_queue(); void push(int num); void pop(); int front(); bool empty(); private: }; Priority_queue::Priority_queue() { tot = 0; } Priority_queue::~Priority_queue() { } void Priority_queue::push(int num) { heap[tot++] = num; int k = tot - 1, t, tmp; while (k > 0) { t = (k - 1) / 2; if (heap[t] < heap[k]) { tmp = heap[t]; heap[t] = heap[k]; heap[k] = tmp; } k = t; } } int Priority_queue::front() { return heap[0]; } bool Priority_queue::empty() { return tot == 0; } void Priority_queue::pop() { heap[0] = heap[--tot]; int k = 0, t, tmp; while ((t = 2 * k + 1) < tot) { if (t + 1 < tot && heap[t + 1] > heap[t])++t; if (heap[k] < heap[t]) { tmp = heap[k]; heap[k] = heap[t]; heap[t] = tmp; k = t; } else break; } } int main() { Priority_queue q; int n, i, x; cin >> n; for (i = 1; i <= n; ++i) { cin >> x; q.push(x); } while (!q.empty()) { cout << q.front() << endl; q.pop(); } return 0; } /* 10 7 11 3 5 4 8 9 20 18 13 */

测试输入：

10 7 11 3 5 4 8 9 20 18 13

测试输出：

20 18 13 11 9 8 7 5 4 3

小根堆：

大根堆是根节点比其儿子结点值要小的二叉堆，故优先队列的队首数值是最小的。具体实现见代码：

#include<iostream> #include<cstdio> using namespace std; const int maxn = 1000; class priority_queue //小根堆，优先队列 { public: priority_queue(); ~priority_queue(); void push(int num); int front(); bool empty(); void pop(); private: int heap[maxn], tot; }; priority_queue::priority_queue() { tot = 0; } priority_queue::~priority_queue() { } bool priority_queue::empty() { return tot == 0; } void priority_queue::push(int num) { heap[tot++] = num; int t, k = tot - 1, tmp; while (k > 0) { //直到小根堆的顶截止 t = (k - 1) / 2; if (heap[t] > heap[k]) { //如果其根的值大于其本身的值，就交换 tmp = heap[t]; heap[t] = heap[k]; heap[k] = tmp; } k = t; } } int priority_queue::front() { return heap[0]; } void priority_queue::pop() { heap[0] = heap[--tot]; int k = 0, t, tmp; while ((t = 2 * k + 1) < tot) { if (t + 1 < tot && heap[t + 1] < heap[t])t++; if (heap[k] > heap[t]) { tmp = heap[t]; heap[t] = heap[k]; heap[k] = tmp; k = t; } else break; } } int main() { priority_queue q; int n, i, x; cin >> n; for (i = 1; i <= n; ++i) { cin >> x; q.push(x); } while (!q.empty()) { cout << q.front() << endl; q.pop(); } return 0; } /* 10 7 11 3 5 4 8 9 20 18 13 */

测试输入：

10 7 11 3 5 4 8 9 20 18 13

测试输出：

3 4 5 7 8 9 11 13 18 20