C++的實現(xiàn)優(yōu)先隊列(Priority?Queue)的實現(xiàn)
一、前言
在 C++ 編程的奇妙世界里，數據結構就像是一個個功能各異的工具，幫助我們高效地處理和組織數據。而在眾多的數據結構中，優(yōu)先隊列（Priority Queue）有著獨特且重要的地位。它們各自有著獨特的工作方式和應用場景，就如同特殊的鑰匙，能為我們開啟解決不同編程難題的大門。
二、優(yōu)先隊列（Priority Queue）：排隊也有 “特權”？
（一）優(yōu)先隊列是啥？
想象一下，你在一個超級特別的隊伍里。這個隊伍里的人可不是按照先來后到排隊的哦??，而是每個人都有一個 “重要程度” 的標簽??。比如說，在醫(yī)院的急診室，重傷的病人就比輕傷的病人更 “重要”，會優(yōu)先得到救治。這就是優(yōu)先隊列的基本概念啦！它是一種數據結構，元素們按照自己的優(yōu)先級排隊，優(yōu)先級最高的元素總是站在隊伍的最前面，等著被處理。
（二）C++ 里怎么用優(yōu)先隊列？
標準模板庫（STL）來幫忙C++ 的 STL 給我們提供了一個超方便的priority_queue類。要用它的話，先把<queue>頭文件包含進來哦??。就像這樣：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
pq.push(5);
pq.push(10);
pq.push(3);
std::cout << "隊首元素（最大值）: " << pq.top() << std::endl;
pq.pop();
std::cout << "隊首元素（最大值）: " << pq.top() << std::endl;
return 0;
}
這里我們創(chuàng)建了一個存整數的優(yōu)先隊列，默認情況下，它就像一個 “選大比賽”，最大的數在隊首哦??。每次push進去一個數，它就會自動按照大小排好隊，top就能看到隊首的最大值，pop就把最大值請出去啦。
想自定義規(guī)則？沒問題！要是你覺得默認的 “選大” 或者 “選小” 規(guī)則不合心意，也可以自己定規(guī)則哦??。這時候就要用到比較函數或者函數對象啦。看下面這個例子，我們來創(chuàng)建一個小頂堆，讓最小的數在隊首：
#include <iostream>
#include <queue>
struct Compare {
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
std::priority_queue<int, std::vector<int>, Compare> pq;
pq.push(5);
pq.push(10);
pq.push(3);
std::cout << "隊首元素（最小值）: " << pq.top() << std::endl;
pq.pop();
std::cout << "隊首元素（最小值）: " << pq.top() << std::endl;
return 0;
}
我們定義了一個Compare結構體，里面的operator()函數就是我們的比較規(guī)則。這樣，優(yōu)先隊列就會按照我們定的規(guī)則來排隊啦。
（三）優(yōu)先隊列內部到底咋回事？
1. 秘密武器：二叉堆（Binary Heap）
其實呀，priority_queue背后是靠二叉堆這個小助手來干活的呢??。二叉堆就像一棵特別的樹，每個節(jié)點都有自己的任務哦。對于大頂堆來說，父節(jié)點就像個小隊長，它的值得比子節(jié)點的值大，這樣才能保證隊里最大的值在最上面呀。小頂堆呢，就剛好相反，父節(jié)點的值要小于等于子節(jié)點的值。
下面是個簡單示意二叉堆節(jié)點結構體的代碼，實際 STL 里的實現(xiàn)更復雜哦：
template<typename T>
struct BinaryHeapNode {
T value;
BinaryHeapNode<T>* left;
BinaryHeapNode<T>* right;
BinaryHeapNode(T val) : value(val), left(nullptr), right(nullptr) {}
};2. 元素進出的 “魔法”
插入（push）元素
當有新元素要加進這個特別的隊伍時，它會先站到隊伍最后面哦。然后呢，它就開始和前面的人比，如果它比前面的人更 “重要”（按堆的規(guī)則），就和前面的人換位置，一直這么比下去，直到找到自己合適的位置，這就叫 “上溯（sift up）” 啦，就好像新隊員要在隊伍里找到自己的等級一樣呢??。
下面是個簡單示例代碼片段，展示插入元素并維護二叉堆性質（假設已有上面那個二叉堆節(jié)點結構體定義哦）：
template<typename T>
void siftUp(BinaryHeapNode<T>* node) {
while (node!= nullptr && node->parent!= nullptr && node->value > node->parent->value) {
// 交換節(jié)點和其父節(jié)點的值
swap(node->value, node->parent->value);
node = node->parent;
}
}
template<typename T>
void pushToHeap(BinaryHeapNode<T>* root, T value) {
// 創(chuàng)建新節(jié)點并插入到堆的末尾
BinaryHeapNode<T>* newNode = new BinaryHeapNode<T>(value);
if (root == nullptr) {
root = newNode;
} else {
// 找到合適的位置插入新節(jié)點（這里簡單假設插入到最后一個葉子節(jié)點位置）
BinaryHeapNode<T>* current = root;
while (current->left!= nullptr && current->right!= nullptr) {
current = current->left;
}
if (current->left == nullptr) {
current->left = newNode;
} else {
current->right = newNode;
}
// 對新插入的節(jié)點進行上溯操作
siftUp(newNode);
}
}刪除（pop）元素
當要處理隊首元素（也就是
pop操作）時，隊伍最后面的那個人會跑到隊首來。但他可能不符合隊首的要求呀，所以他就得和下面的人比，如果下面的人比他更 “適合” 隊首，就和下面的人換位置，一直比到他找到自己合適的位置為止，這就是 “下溯（sift down）” 的過程啦??。
下面是個簡單示例代碼片段，展示刪除堆頂元素并維護二叉堆性質（同樣假設已有上面那個二叉堆節(jié)點結構體定義哦）：
template<typename T>
void siftDown(BinaryHeapNode<T>* node) {
while (node!= nullptr) {
BinaryHeapNode<T>* largest = node;
if (node->left!= nullptr && node->left->value > largest->value) {
largest = node->left;
}
if (node->right!= nullptr && node->right->value > largest->value) {
largest = node->right;
}
if (largest!= node) {
// 交換節(jié)點和最大子節(jié)點的值
swap(node->value, largest->value);
node = largest;
} else {
break;
}
}
}
template<typename T>
T popFromHeap(BinaryHeapNode<T>* root) {
if (root == nullptr) {
throw runtime_error("堆為空");
}
T rootValue = root->value;
// 將堆的最后一個節(jié)點的值賦給堆頂
BinaryHeapNode<T>* lastNode = findLastNode(root);
root->value = lastNode->value;
// 刪除最后一個節(jié)點（這里簡單假設能正確刪除，實際可能更復雜）
delete lastNode;
// 對新的堆頂節(jié)點進行下溯操作
siftDown(root);
return rootValue;
}在這代碼里，popFromHeap函數就是用來刪二叉堆的堆頂元素的，刪完后用siftDown函數來保證二叉堆還是符合大頂堆的條件呢。
（四）優(yōu)先隊列都在哪里大顯身手？
1. 任務調度：誰先誰后安排好
在操作系統(tǒng)或者任務管理系統(tǒng)里呀，任務就像一群等著被處理的小士兵????。每個任務都有自己的優(yōu)先級，比如緊急任務優(yōu)先級高，普通任務優(yōu)先級低。優(yōu)先隊列就像個聰明的指揮官，把任務按優(yōu)先級排好隊，處理器就可以按順序先處理重要的任務啦，這樣系統(tǒng)就能高效地運行咯，就跟快遞分揀中心會優(yōu)先處理加急件一樣呢??。
下面是個簡單的任務調度模擬代碼示例，用優(yōu)先隊列來實現(xiàn)任務按優(yōu)先級排序處理哦：
#include <iostream>
#include <queue>
#include <string>
using namespace std;
// 任務結構體
struct Task {
string name;
int priority;
Task(const string& n, int p) : name(n), priority(p) {}
};
// 自定義比較函數，按照任務優(yōu)先級從高到低排序
struct TaskCompare {
bool operator()(const Task& t1, const Task& t2) {
return t1.priority < t2.priority;
}
};
int main() {
// 創(chuàng)建任務優(yōu)先隊列
priority_queue<Task, vector<Task>, TaskCompare> taskQueue;
// 添加一些任務到隊列
taskQueue.push(Task("任務1", 5));
taskQueue.push(Task("任務2", 3));
taskQueue.push(Task("任務3", 8));
// 模擬處理器處理任務
while (!taskQueue.empty()) {
Task currentTask = taskQueue.top();
cout << "正在處理任務: " << currentTask.name << "，優(yōu)先級: " << currentTask.priority << endl;
taskQueue.pop();
}
return 0;
}
在這個例子里，我們先定義了Task結構體來表示任務，有任務名字和優(yōu)先級兩個屬性哦。然后通過自定義的TaskCompare比較函數，讓優(yōu)先隊列按任務優(yōu)先級從高到低給任務排隊。最后模擬處理器依次處理隊列里的任務呢。
2. 圖算法中的 “指路明燈”
在一些圖算法里呀，比如 Dijkstra 算法求單源最短路徑，優(yōu)先隊列可真是個大功臣呢??。想象一下你在一個迷宮里找出口，每個路口都有不同的距離標記。算法得不斷選離起點最近的未訪問路口繼續(xù)探索呀，優(yōu)先隊列就能很快告訴算法哪個路口離起點最近，就像個導航儀一樣，讓算法能高效地找到最短路徑呢??。
下面是個簡單的 Dijkstra 算法示例，用優(yōu)先隊列來輔助找到從一個源點到其他節(jié)點的最短路徑哦（這只是個簡化示例，實際應用可能更復雜啦）：
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 節(jié)點結構體
struct Node {
int id;
vector<Node*> neighbors;
int distance;
Node(int i) : id(i), distance(INT_MAX) {}
};
// 自定義比較函數，按照節(jié)點距離從小到大排序
struct NodeCompare {
bool operator()(const Node* n1, const Node* n2) {
return n1->distance > n2->distance;
}
};
// Dijkstra算法實現(xiàn)
void dijkstra(Node* source) {
// 創(chuàng)建優(yōu)先隊列，按照節(jié)點距離排序
priority_queue<Node*, vector<Node*>, NodeCompare> pq;
// 將源點加入隊列，并設置其距離為0
source->distance = 0;
pq.push(source);
// 用于記錄已訪問過的節(jié)點
unordered_map<int, bool> visited;
while (!pq.empty()) {
Node* currentNode = pq.top();
pq.pop();
// 如果節(jié)點已經訪問過，跳過
if (visited[currentNode->id]) {
continue;
}
// 標記當前節(jié)點為已訪問
visited[currentNode->id] = true;
// 更新當前節(jié)點鄰居的距離
for (Node* neighbor : currentNode->neighbors) {
int newDistance = currentNode->日前距離 + 1;
if (newDistance < neighbor->distance) {
neighbor->distance = newDistance;
pq.push(neighbor);
}
}
}
}
int main() {
// 創(chuàng)建一些節(jié)點
Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
// 構建節(jié)點之間的連接關系
node1->日前鄰居.push_back(node2);
node1->日前鄰居.push_back(node3);
node2->日前鄰居.push_back(node3);
// 運行Dijkstra算法
dijkstra(node1);
// 輸出節(jié)點到源點的距離
cout << "節(jié)點2到源點的距離: " << node2->distance << endl;
cout << "節(jié)點3到源點的距離: " << node3->distance << endl;
return 0;
} 在這個例子里，我們先定義了Node結構體來表示圖中的節(jié)點，有節(jié)點 ID、鄰居節(jié)點列表和到源點的距離這些屬性哦。然后通過自定義的NodeCompare比較函數，讓優(yōu)先隊列按節(jié)點距離從小到大給節(jié)點排隊。接著在 Dijkstra 算法里，利用優(yōu)先隊列高效地選離源點最近的未訪問節(jié)點進行處理，這樣就能找到從源點到其他節(jié)點的最短路徑啦。
3. 數據壓縮：讓數據 “瘦身” 有妙招
在哈夫曼編碼這個數據壓縮方法里呀，優(yōu)先隊列也發(fā)揮著重要作用呢??。它就像個聰明的小助手，幫我們構建哈夫曼樹。在構建過程中，它會選出現(xiàn)頻率最低的兩個字符，把它們合并成一個新的 “組合字符”，然后繼續(xù)選頻率最低的進行合并，直到構建出完整的哈夫曼樹。最后根據這棵樹給每個字符分配不同長度的編碼，這樣就能讓數據占用更少的空間啦??。
下面是個簡單的哈夫曼編碼構建示例，用優(yōu)先隊列來輔助構建哈夫曼樹哦（這也是個簡化示例，實際應用可能更復雜啦）：
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;
// 哈夫曼樹節(jié)點結構體
struct HuffmanNode {
char data;
int frequency;
HuffmanNode* left;
HuffmanNode* left右;
HuffmanNode(char d, int f) : data(d), frequency(f), left(nullptr), left右(nullptr) {}
}
// 自定義比較函數，按照節(jié)點頻率從小到大排序
struct HuffmanNodeCompare {
bool operator()(const HuffmanNode* n1, const HuffmanNode* n2) {
return n1->frequency > n2->frequency;
}
};
// 構建哈夫曼樹
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& frequencyMap) {
// 創(chuàng)建優(yōu)先隊列，按照節(jié)點頻率排序
priority_queue<HuffmanNode*, vector<H夫曼Node*>, HuffmanNodeCompare> pq;
// 將每個字符及其頻率對應的節(jié)點加入隊列
for (const auto& pair : frequencyMap) {
pq.push(new HuffmanNode(pair.first, pair.second));
}
while (pq.size() > 1) {
// 取出頻率最低的兩個節(jié)點
HuffmanNode* leftNode = pq.top();
pq.pop();
HuffmanNode* rightNode = pq.top();
pq.pop();
// 創(chuàng)建新的父節(jié)點，頻率為兩個子節(jié)點頻率之和
HuffmanNode* parentNode = new HuffmanNode('\0', leftNode->frequency + rightNode->frequency);
parentNode->left = leftNode;
parentNode->right = rightNode;
// 將父節(jié)點加入隊列
pq.push(parentNode);
}
return pq.top();
}
int main() {
// 假設這里有個字符頻率映射表
unordered_map<char, int> frequencyMap = {
{'a', 5},
{'b', 3},
{'c', 8}
};
// 構建哈夫曼樹
HuffmanNode* huffmanTree = buildHuffmanTree(frequencyMap);
// 這里可以根據哈夫曼樹進一步處理，比如生成編碼等，但為了簡化先不展示啦
return 0;
} 在這個例子里，我們先定義了HuffmanNode結構體來表示哈夫曼樹的節(jié)點，有字符數據、頻率、左右子節(jié)點這些屬性哦。然后通過自定義的HuffmanNodeCompare比較函數，讓優(yōu)先隊列按節(jié)點頻率從小到大給節(jié)點排隊。接著在構建哈夫曼樹的過程中，利用優(yōu)先隊列選出頻率最低的兩個節(jié)點合并成新節(jié)點，一直重復這個過程直到構建出完整的哈夫曼樹呢。
到此這篇關于C++的實現(xiàn)優(yōu)先隊列（Priority Queue）的文章就介紹到這了,更多相關C++ 優(yōu)先隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了C語言中數據的存儲，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助，希望能夠給你帶來幫助2021-11-11
C語言中的指針和數組是兩個重要的數據結構，它們在內存管理和數據存儲方面有許多相似之處，但也存在一些關鍵的區(qū)別，本文就來介紹一下C語言中的指針和數組有什么區(qū)別，具有一定的參考價值，感興趣的可以了解一下2023-09-09
strcpy 和strcnpy函數是字符串復制函數。接下來通過本文給大家介紹c語言中的strcpy和strncpy字符串函數使用，感興趣的朋友跟隨小編要求看看吧2018-10-10
運算符重載是一種形式的C++多態(tài)。運算符重載將重載的概念擴展到運算符上，允許賦予C++運算符多種含義2014-03-03
這篇文章主要為大家詳細介紹了C++中動態(tài)內存管理相關資料，文中示例代碼講解詳細，對我們學習C++具有一定幫助，感興趣的小伙伴快跟隨小編一起學習2023-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)圖書管理系統(tǒng)開發(fā)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要為大家介紹了C++測試框架GoogleTest入門基礎，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
這篇文章主要為大家詳細介紹了用C語言實現(xiàn)2048游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要給大家介紹了關于C++中volatile關鍵字及常見的誤解的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-05-05
這篇文章主要為大家詳細介紹了使用C語言實現(xiàn)五子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08