目录
引言
优先队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都有一个优先级。与普通队列不同，优先队列中的元素不是按照先进先出的原则出队，而是按照优先级的高低出队。本文将详细介绍优先队列的实现，包括其底层数据结构——堆的原理，以及完整的C++实现代码。
堆的基本概念与特性
堆是一种完全二叉树，分为最大堆和最小堆。最大堆中父节点值大于等于子节点，最小堆中父节点值小于等于子节点。这种特性使得堆能高效地维护数据的优先级。
完全二叉树的数组表示法通过下标关系定位父子节点：
- 已知子节点下标i：父节点索引：
(i - 1) / 2； - 已知父节点下标i：左子节点：
2*i + 1，右子节点：2*i + 2；
堆的插入与向上调整
插入操作将新元素置于数组末尾，通过向上调整（adjustUp）维护堆结构：
- 比较新节点与父节点的值；
- 若违反堆序（最大堆中子节点更大，或最小堆中子节点更小），交换两者；
- 重复过程直至根节点或堆序满足。
堆的删除与向下调整
删除堆顶元素时，将末尾元素移至堆顶，通过向下调整（adjustDown）恢复堆结构：
- 从根节点开始，比较其与较大（最大堆）或较小（最小堆）子节点的值；
- 若违反堆序，交换两者并继续向下检查；
- 终止于叶子节点或堆序满足时。
优先队列的设计思路
优先队列基于堆实现，支持高效获取最高/低优先级元素。关键设计包括：
模板参数设计
T：元素类型。Container：默认vector，需支持随机访问和动态扩容。Compare：比较器，默认Less<T>实现最大堆，Greater<T>实现最小堆。
比较器的作用
通过模板参数Compare实现灵活的大小比较策略：
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template <class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
核心接口实现
push
插入元素并向上调整堆：
public:
void push(T data)
{
_con.push_back(data);
adjustUp();
}
private:
void adjustUp()
{
int child = _con.size() - 1;
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else break;
}
}pop
移除堆顶元素并向下调整堆：
public:
T pop()
{
T data = _con.front();
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjustDown();
return data;
}
private:
void adjustDown()
{
int parent = 0;
int child = 1;
while (child < size())
{
if (child + 1 < size())
{
if (com(_con[child], _con[child + 1]))
{
child = child + 1;
}
}
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}top
访问堆顶元素（即数组首元素）
T top() { return _con.front(); }附录(完整代码)
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template <class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template <class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
priority_queue() {}
priority_queue(const Container &con)
{
for (auto& item : con)
{
push(item);
}
}
void push(T data)
{
_con.push_back(data);
adjustUp();
}
T pop()
{
T data = _con.front();
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjustDown();
return data;
}
T top() { return _con.front(); }
size_t size() { return _con.size(); }
bool empty() { return _con.empty(); }
private:
void adjustUp()
{
int child = _con.size() - 1;
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else break;
}
}
void adjustDown()
{
int parent = 0;
int child = 1;
while (child < size())
{
if (child + 1 < size())
{
if (com(_con[child], _con[child + 1]))
{
child = child + 1;
}
}
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else break;
}
}
private:
Container _con;
Compare com;
};