优先级队列

目录

引言

1. 优先级队列的核心概念

2. 比较器模板类设计

3. 优先级队列模板类实现

3.1 类模板定义

3.2 堆调整核心函数

3.2.1 向下调整函数  AdjustDown 

3.2.2 向上调整函数  AdjustUp 

3.3 成员函数实现

3.3.1 迭代器构造函数

3.3.2 元素插入函数  Push 

3.3.3 元素删除函数  pop 

3.3.4 其他辅助函数

4. 测试与验证

5. 总结

---

引言

---

优先级队列（ priority_queue ）是一种特殊的容器适配器，在C++标准库中被广泛应用。与普通队列“先进先出”的特性不同，优先级队列每次从队首取出的元素总是队列中优先级最高的元素。本文将深入剖析优先级队列的底层实现原理，并通过完整的C++代码，手把手教你实现一个自定义的优先级队列模板类。

1. 优先级队列的核心概念

优先级队列通常基于堆数据结构实现，堆是一种完全二叉树，分为大顶堆和小顶堆：

- 大顶堆：每个父节点的值都大于或等于其子节点的值，因此堆顶元素是整个堆中的最大值

- 小顶堆：每个父节点的值都小于或等于其子节点的值，堆顶元素是最小值

C++标准库中的 priority_queue 默认实现为大顶堆。我们的自定义实现将支持通过自定义比较器，灵活切换大顶堆和小顶堆模式。

2. 比较器模板类设计

首先定义两个比较器模板类，用于定义元素之间的比较规则：

cpp// 小于比较器模板类，用于构建小顶堆template<class T>class Less{public:// 重载()运算符实现比较逻辑bool operator()(const T& x, const T& y){return x < y;}};// 大于比较器模板类，用于构建大顶堆template<class T>class GreaTor{public:bool operator()(const T& x, const T& y){return x > y;}};

通过重载 () 运算符，我们将比较逻辑封装成可调用对象。 Less 类实现小于比较，适用于小顶堆； GreaTor 类实现大于比较，适用于大顶堆。

3. 优先级队列模板类实现

3.1 类模板定义

cppnamespace ldg{// 优先级队列模板类// T: 元素类型// X: 底层存储容器类型，默认使用std::vector// Compare: 比较器类型，默认使用Lesstemplate<class T, class X = std::vector<T>, class Compare = Less<T>>class priority_queue{private:X _con; // 底层存储容器// 堆调整函数声明void AdjustDown(int parent);void AdjustUp(int child);public:// 构造函数、插入、删除等成员函数声明template<class Intiterator>priority_queue(Intiterator first, Intiterator last);void Push(const T& x);priority_queue();void pop();const T& top();bool empty();size_t size();};}

通过模板参数 T 、 X 和 Compare ，我们实现了类型、容器和比较规则的高度可定制化。

3.2 堆调整核心函数

3.2.1 向下调整函数  AdjustDown 

cpptemplate<class T, class X, class Compare>void ldg::priority_queue<T, X, Compare>::AdjustDown(int parent){Compare com; // 创建比较器对象int child = parent * 2 + 1; // 左孩子索引while (child < _con.size()) // 确保孩子节点在有效范围内{// 如果存在右孩子且右孩子优先级更高if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++; // 选择右孩子}// 如果父节点优先级低于孩子节点if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]); // 交换父子节点parent = child; // 更新父节点位置child = parent * 2 + 1; // 更新孩子节点位置}else {break; // 堆性质已满足}}}

该函数从指定父节点开始，通过比较和交换操作，将元素下沉到合适位置，确保以 parent 为根的子树满足堆的性质。

3.2.2 向上调整函数  AdjustUp 

cpptemplate<class T, class X, class Compare>void ldg::priority_queue<T, X, Compare>::AdjustUp(int child){Compare com;int parent = (child - 1) / 2; // 计算父节点索引while (child > 0) // 向上调整直到根节点{// 如果孩子节点优先级高于父节点if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]); // 交换父子节点child = parent; // 更新孩子节点位置parent = (child - 1) / 2; // 更新父节点位置}else {break; // 堆性质已满足}}}

 AdjustUp 函数从指定孩子节点开始，将元素上浮，确保从该节点到根节点路径上的所有节点满足堆的性质。

3.3 成员函数实现

3.3.1 迭代器构造函数

cpptemplate<class T, class X, class Compare>template<class Intiterator>ldg::priority_queue<T, X, Compare>::priority_queue(Intiterator first, Intiterator last){while (first != last){_con.push_back(*first); // 插入元素到容器first++;}// 建堆操作for (int i = (_con.size() - 2) / 2; i >= 0; i--){AdjustDown(i); // 从最后一个非叶子节点开始调整}}

该构造函数通过迭代器范围初始化队列，并通过 AdjustDown 函数将容器中的元素构建成堆。

3.3.2 元素插入函数  Push 

cpptemplate<class T, class X, class Compare>void ldg::priority_queue<T, X, Compare>::Push(const T& x){_con.push_back(x); // 添加元素到容器末尾AdjustUp(_con.size() - 1); // 向上调整新元素}

新元素插入后，通过 AdjustUp 函数上浮到正确位置，保持堆的性质。

3.3.3 元素删除函数  pop 

cpptemplate<class T, class X, class Compare>void ldg::priority_queue<T, X, Compare>::pop(){std::swap(_con[0], _con[_con.size() - 1]); // 交换堆顶和堆尾_con.pop_back(); // 删除堆尾元素AdjustDown(0); // 向下调整堆顶}

删除操作先将堆顶元素与堆尾元素交换，移除堆尾元素后，通过 AdjustDown 函数重新调整堆顶元素。

3.3.4 其他辅助函数

cpptemplate<class T, class X, class Compare>const T& ldg::priority_queue<T, X, Compare>::top(){return _con[0]; // 返回堆顶元素}template<class T, class X, class Compare>bool ldg::priority_queue<T, X, Compare>::empty(){return _con.empty(); // 判断容器是否为空}template<class T, class X, class Compare>size_t ldg::priority_queue<T, X, Compare>::size(){return _con.size(); // 返回容器大小}

这些函数分别用于获取堆顶元素、判断队列是否为空以及获取队列大小。

4. 测试与验证

cppnamespace ldg{void test(){priority_queue<int> pq; // 使用默认小顶堆pq.Push(5);pq.Push(9);pq.Push(3);pq.Push(1);pq.Push(5);pq.Push(6);pq.Push(0);pq.Push(4);std::cout << "小顶堆输出: ";while (!pq.empty()){std::cout << pq.top() << " ";pq.pop();}std::cout << std::endl;// 使用大顶堆测试priority_queue<int, std::vector<int>, GreaTor<int>> pq2;pq2.Push(5);pq2.Push(9);pq2.Push(3);pq2.Push(1);pq2.Push(5);pq2.Push(6);pq2.Push(0);pq2.Push(4);std::cout << "大顶堆输出: ";while (!pq2.empty()){std::cout << pq2.top() << " ";pq2.pop();}std::cout << std::endl;}}int main(){ldg::test();return 0;}

通过 test 函数，我们分别测试了默认小顶堆和自定义大顶堆的功能，验证了优先级队列的正确性。

5. 总结

本文通过详细的代码解析和注释，完整实现了一个功能强大的C++优先级队列模板类。通过自定义比较器，我们可以灵活控制堆的类型（大顶堆/小顶堆），同时深入理解了堆调整的核心算法。这种自定义实现不仅有助于掌握数据结构原理，也为实际项目中灵活使用优先级队列提供了坚实基础。