目錄

引言

堆的基本概念與特性

?堆的插入與向上調整

堆的刪除與向下調整

優先隊列的設計思路

模板參數設計

?比較器的作用?

核心接口實現

push

pop

top

附錄(完整代碼)?

---

引言

????????優先隊列（Priority Queue）是一種特殊的隊列數據結構，其中每個元素都有一個優先級。與普通隊列不同，優先隊列中的元素不是按照先進先出的原則出隊，而是按照優先級的高低出隊。本文將詳細介紹優先隊列的實現，包括其底層數據結構——堆的原理，以及完整的C++實現代碼。

堆的基本概念與特性

????????堆是一種完全二叉樹，分為最大堆和最小堆。最大堆中父節點值大于等于子節點，最小堆中父節點值小于等于子節點。這種特性使得堆能高效地維護數據的優先級。

????????完全二叉樹的數組表示法通過下標關系定位父子節點：

• 已知子節點下標i：父節點索引：(i - 1) / 2；
• 已知父節點下標i：左子節點：2*i + 1，右子節點：2*i + 2；

?堆的插入與向上調整

插入操作將新元素置于數組末尾，通過向上調整（adjustUp）維護堆結構：

1. 比較新節點與父節點的值；
2. 若違反堆序（最大堆中子節點更大，或最小堆中子節點更小），交換兩者；
3. 重復過程直至根節點或堆序滿足。

堆的刪除與向下調整

刪除堆頂元素時，將末尾元素移至堆頂，通過向下調整（adjustDown）恢復堆結構：

1. 從根節點開始，比較其與較大（最大堆）或較小（最小堆）子節點的值；
2. 若違反堆序，交換兩者并繼續向下檢查；
3. 終止于葉子節點或堆序滿足時。

優先隊列的設計思路

????????優先隊列基于堆實現，支持高效獲取最高/低優先級元素。關鍵設計包括：

模板參數設計

• 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;
};