2014.06.15 22:14
简介：
堆是一种非常实用的数据结构，其中以二叉堆最为常用。二叉堆可以看作一棵完全二叉树，每个节点的键值都大于（小于）其子节点，但左右孩子之间不需要有序。我们关心的通常只有堆顶的元素，而整个堆则被封装起来，保存在一个数组中。
图示：
下图是一个最大堆：
实现：
优先队列是STL中最常用的工具之一，许多算法的优化都要利用堆，使用的工具就是优先队列。STL中的优先队列通过仿函数来定义比较算法，此处我偷懒用了“<”运算符。关于使用仿函数的好处，我之后如果有时间深入学习STL的话，再写博文分析吧。
// My implementation for priority queue using binary heap.
#include <iostream>
#include <string>
#include <vector>
using namespace std; template <class T>
class PriorityQueue {
public:
PriorityQueue() {
m_data.push_back();
} PriorityQueue(const vector<T> &data) {
m_data.push_back();
for (size_t i = ; i < data.size(); ++i) {
m_data.push_back(data[i]);
}
_makeHeap();
} bool empty() {
return m_data.size() == ;
} size_t size() {
return m_data.size() - ;
} T top() {
return m_data[];
} void push(const T &val) {
m_data.push_back(val); int n = size();
int i = n; while (i > ) {
if (m_data[i / ] < m_data[i]) {
_swap(m_data[i / ], m_data[i]);
i /= ;
} else {
break;
}
}
} void pop() {
int n = size();
m_data[] = m_data[n];
m_data.pop_back();
--n; int i = ;
T max_val;
while (i * <= n) {
max_val = i * == n ? m_data[i * ] : _max(m_data[i * ], m_data[i * + ]);
if (m_data[i] < max_val) {
if (max_val == m_data[i * ] || i * == n) {
_swap(m_data[i], m_data[i * ]);
i = i * ;
} else {
_swap(m_data[i], m_data[i * + ]);
i = i * + ;
}
} else {
break;
}
}
} void clear() {
m_data.resize();
} ~PriorityQueue() {
m_data.clear();
}
private:
vector<T> m_data; T _max(const T &x, const T &y) {
return x > y ? x : y;
} void _swap(T &x, T &y) {
T tmp; tmp = x;
x = y;
y = tmp;
} void _makeHeap() {
int n = size();
int i, j;
T max_val; for (j = n / ; j >= ; --j) {
i = j;
while (i * <= n) {
max_val = i * == n ? m_data[i * ] : _max(m_data[i * ], m_data[i * + ]);
if (m_data[i] < max_val) {
if (max_val == m_data[i * ] || i * == n) {
_swap(m_data[i], m_data[i * ]);
i = i * ;
} else {
_swap(m_data[i], m_data[i * + ]);
i = i * + ;
}
} else {
break;
}
}
} n = size();
cout << '[';
for (int i = ; i <= n; ++i) {
cout << m_data[i] << ' ';
}
cout << ']' << endl;
}
}; int main()
{
vector<int> v;
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
PriorityQueue<int> pq(v);
string s;
int n; while (cin >> s) {
if (s == "push") {
cin >> n;
pq.push(n);
} else if (s == "pop") {
pq.pop();
} else if (s == "top") {
cout << pq.top() << endl;
} else if (s == "end") {
while (!pq.empty()) {
pq.pop();
}
break;
}
} return ;
}