C++的實(shí)現(xiàn)優(yōu)先隊(duì)列(Priority?Queue)的實(shí)現(xiàn)

更新時(shí)間：2025年06月05日 09:21:20 作者：A?charmer

本文主要介紹了C++的實(shí)現(xiàn)優(yōu)先隊(duì)列(Priority?Queue)的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

一、前言

在 C++ 編程的奇妙世界里，數(shù)據(jù)結(jié)構(gòu)就像是一個(gè)個(gè)功能各異的工具，幫助我們高效地處理和組織數(shù)據(jù)。而在眾多的數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊(duì)列（Priority Queue）有著獨(dú)特且重要的地位。它們各自有著獨(dú)特的工作方式和應(yīng)用場景，就如同特殊的鑰匙，能為我們開啟解決不同編程難題的大門。

?? priority_queue文檔介紹

二、優(yōu)先隊(duì)列（Priority Queue）：排隊(duì)也有 “特權(quán)”？

（一）優(yōu)先隊(duì)列是啥？

想象一下，你在一個(gè)超級特別的隊(duì)伍里。這個(gè)隊(duì)伍里的人可不是按照先來后到排隊(duì)的哦??，而是每個(gè)人都有一個(gè) “重要程度” 的標(biāo)簽??。比如說，在醫(yī)院的急診室，重傷的病人就比輕傷的病人更 “重要”，會優(yōu)先得到救治。這就是優(yōu)先隊(duì)列的基本概念啦！它是一種數(shù)據(jù)結(jié)構(gòu)，元素們按照自己的優(yōu)先級排隊(duì)，優(yōu)先級最高的元素總是站在隊(duì)伍的最前面，等著被處理。

（二）C++ 里怎么用優(yōu)先隊(duì)列？

標(biāo)準(zhǔn)模板庫（STL）來幫忙C++ 的 STL 給我們提供了一個(gè)超方便的priority_queue類。要用它的話，先把<queue>頭文件包含進(jìn)來哦??。就像這樣：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(5);
    pq.push(10);
    pq.push(3);

    std::cout << "隊(duì)首元素（最大值）: " << pq.top() << std::endl;

    pq.pop();

    std::cout << "隊(duì)首元素（最大值）: " << pq.top() << std::endl;

    return 0;
}

這里我們創(chuàng)建了一個(gè)存整數(shù)的優(yōu)先隊(duì)列，默認(rèn)情況下，它就像一個(gè) “選大比賽”，最大的數(shù)在隊(duì)首哦??。每次push進(jìn)去一個(gè)數(shù)，它就會自動(dòng)按照大小排好隊(duì)，top就能看到隊(duì)首的最大值，pop就把最大值請出去啦。

想自定義規(guī)則？沒問題！要是你覺得默認(rèn)的 “選大” 或者 “選小” 規(guī)則不合心意，也可以自己定規(guī)則哦??。這時(shí)候就要用到比較函數(shù)或者函數(shù)對象啦。看下面這個(gè)例子，我們來創(chuàng)建一個(gè)小頂堆，讓最小的數(shù)在隊(duì)首：

#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 << "隊(duì)首元素（最小值）: " << pq.top() << std::endl;

    pq.pop();

    std::cout << "隊(duì)首元素（最小值）: " << pq.top() << std::endl;

    return 0;
}

我們定義了一個(gè)Compare結(jié)構(gòu)體，里面的operator()函數(shù)就是我們的比較規(guī)則。這樣，優(yōu)先隊(duì)列就會按照我們定的規(guī)則來排隊(duì)啦。

（三）優(yōu)先隊(duì)列內(nèi)部到底咋回事？

1. 秘密武器：二叉堆（Binary Heap）

其實(shí)呀，priority_queue背后是靠二叉堆這個(gè)小助手來干活的呢??。二叉堆就像一棵特別的樹，每個(gè)節(jié)點(diǎn)都有自己的任務(wù)哦。對于大頂堆來說，父節(jié)點(diǎn)就像個(gè)小隊(duì)長，它的值得比子節(jié)點(diǎn)的值大，這樣才能保證隊(duì)里最大的值在最上面呀。小頂堆呢，就剛好相反，父節(jié)點(diǎn)的值要小于等于子節(jié)點(diǎn)的值。

下面是個(gè)簡單示意二叉堆節(jié)點(diǎn)結(jié)構(gòu)體的代碼，實(shí)際 STL 里的實(shí)現(xiàn)更復(fù)雜哦：

template&lt;typename T&gt;
struct BinaryHeapNode {
    T value;
    BinaryHeapNode&lt;T&gt;* left;
    BinaryHeapNode&lt;T&gt;* right;

    BinaryHeapNode(T val) : value(val), left(nullptr), right(nullptr) {}
};

2. 元素進(jìn)出的 “魔法”

插入（push）元素

當(dāng)有新元素要加進(jìn)這個(gè)特別的隊(duì)伍時(shí)，它會先站到隊(duì)伍最后面哦。然后呢，它就開始和前面的人比，如果它比前面的人更 “重要”（按堆的規(guī)則），就和前面的人換位置，一直這么比下去，直到找到自己合適的位置，這就叫 “上溯（sift up）” 啦，就好像新隊(duì)員要在隊(duì)伍里找到自己的等級一樣呢??。

下面是個(gè)簡單示例代碼片段，展示插入元素并維護(hù)二叉堆性質(zhì)（假設(shè)已有上面那個(gè)二叉堆節(jié)點(diǎn)結(jié)構(gòu)體定義哦）：

template<typename T>
void siftUp(BinaryHeapNode<T>* node) {
    while (node!= nullptr && node->parent!= nullptr && node->value > node->parent->value) {
        // 交換節(jié)點(diǎn)和其父節(jié)點(diǎn)的值
        swap(node->value, node->parent->value);
        node = node->parent;
    }
}

template<typename T>
void pushToHeap(BinaryHeapNode<T>* root, T value) {
    // 創(chuàng)建新節(jié)點(diǎn)并插入到堆的末尾
    BinaryHeapNode<T>* newNode = new BinaryHeapNode<T>(value);
    if (root == nullptr) {
        root = newNode;
    } else {
        // 找到合適的位置插入新節(jié)點(diǎn)（這里簡單假設(shè)插入到最后一個(gè)葉子節(jié)點(diǎn)位置）
        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é)點(diǎn)進(jìn)行上溯操作
        siftUp(newNode);
    }
}

刪除（pop）元素

當(dāng)要處理隊(duì)首元素（也就是pop操作）時(shí)，隊(duì)伍最后面的那個(gè)人會跑到隊(duì)首來。但他可能不符合隊(duì)首的要求呀，所以他就得和下面的人比，如果下面的人比他更 “適合” 隊(duì)首，就和下面的人換位置，一直比到他找到自己合適的位置為止，這就是 “下溯（sift down）” 的過程啦??。

下面是個(gè)簡單示例代碼片段，展示刪除堆頂元素并維護(hù)二叉堆性質(zhì)（同樣假設(shè)已有上面那個(gè)二叉堆節(jié)點(diǎn)結(jié)構(gòu)體定義哦）：

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é)點(diǎn)和最大子節(jié)點(diǎn)的值
            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;
    // 將堆的最后一個(gè)節(jié)點(diǎn)的值賦給堆頂
    BinaryHeapNode<T>* lastNode = findLastNode(root);
    root->value = lastNode->value;

    // 刪除最后一個(gè)節(jié)點(diǎn)（這里簡單假設(shè)能正確刪除，實(shí)際可能更復(fù)雜）
    delete lastNode;

    // 對新的堆頂節(jié)點(diǎn)進(jìn)行下溯操作
    siftDown(root);

    return rootValue;
}

在這代碼里，popFromHeap函數(shù)就是用來刪二叉堆的堆頂元素的，刪完后用siftDown函數(shù)來保證二叉堆還是符合大頂堆的條件呢。

（四）優(yōu)先隊(duì)列都在哪里大顯身手？

1. 任務(wù)調(diào)度：誰先誰后安排好

在操作系統(tǒng)或者任務(wù)管理系統(tǒng)里呀，任務(wù)就像一群等著被處理的小士兵??‍??。每個(gè)任務(wù)都有自己的優(yōu)先級，比如緊急任務(wù)優(yōu)先級高，普通任務(wù)優(yōu)先級低。優(yōu)先隊(duì)列就像個(gè)聰明的指揮官，把任務(wù)按優(yōu)先級排好隊(duì)，處理器就可以按順序先處理重要的任務(wù)啦，這樣系統(tǒng)就能高效地運(yùn)行咯，就跟快遞分揀中心會優(yōu)先處理加急件一樣呢??。

下面是個(gè)簡單的任務(wù)調(diào)度模擬代碼示例，用優(yōu)先隊(duì)列來實(shí)現(xiàn)任務(wù)按優(yōu)先級排序處理哦：

#include <iostream>
#include <queue>
#include <string>

using namespace std;

// 任務(wù)結(jié)構(gòu)體
struct Task {
    string name;
    int priority;

    Task(const string& n, int p) : name(n), priority(p) {}
};

// 自定義比較函數(shù)，按照任務(wù)優(yōu)先級從高到低排序
struct TaskCompare {
    bool operator()(const Task& t1, const Task& t2) {
        return t1.priority < t2.priority;
    }
};

int main() {
    // 創(chuàng)建任務(wù)優(yōu)先隊(duì)列
    priority_queue<Task, vector<Task>, TaskCompare> taskQueue;

    // 添加一些任務(wù)到隊(duì)列
    taskQueue.push(Task("任務(wù)1", 5));
    taskQueue.push(Task("任務(wù)2", 3));
    taskQueue.push(Task("任務(wù)3", 8));

    // 模擬處理器處理任務(wù)
    while (!taskQueue.empty()) {
        Task currentTask = taskQueue.top();
        cout << "正在處理任務(wù): " << currentTask.name << "，優(yōu)先級: " << currentTask.priority << endl;
        taskQueue.pop();
    }

    return 0;
}

在這個(gè)例子里，我們先定義了Task結(jié)構(gòu)體來表示任務(wù)，有任務(wù)名字和優(yōu)先級兩個(gè)屬性哦。然后通過自定義的TaskCompare比較函數(shù)，讓優(yōu)先隊(duì)列按任務(wù)優(yōu)先級從高到低給任務(wù)排隊(duì)。最后模擬處理器依次處理隊(duì)列里的任務(wù)呢。

2. 圖算法中的 “指路明燈”

在一些圖算法里呀，比如 Dijkstra 算法求單源最短路徑，優(yōu)先隊(duì)列可真是個(gè)大功臣呢??。想象一下你在一個(gè)迷宮里找出口，每個(gè)路口都有不同的距離標(biāo)記。算法得不斷選離起點(diǎn)最近的未訪問路口繼續(xù)探索呀，優(yōu)先隊(duì)列就能很快告訴算法哪個(gè)路口離起點(diǎn)最近，就像個(gè)導(dǎo)航儀一樣，讓算法能高效地找到最短路徑呢??。

下面是個(gè)簡單的 Dijkstra 算法示例，用優(yōu)先隊(duì)列來輔助找到從一個(gè)源點(diǎn)到其他節(jié)點(diǎn)的最短路徑哦（這只是個(gè)簡化示例，實(shí)際應(yīng)用可能更復(fù)雜啦）：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 節(jié)點(diǎn)結(jié)構(gòu)體
struct Node {
    int id;
    vector<Node*> neighbors;
    int distance;

    Node(int i) : id(i), distance(INT_MAX) {}
};

// 自定義比較函數(shù)，按照節(jié)點(diǎn)距離從小到大排序
struct NodeCompare {
    bool operator()(const Node* n1, const Node* n2) {
        return n1->distance > n2->distance;
    }
};

// Dijkstra算法實(shí)現(xiàn)
void dijkstra(Node* source) {
    // 創(chuàng)建優(yōu)先隊(duì)列，按照節(jié)點(diǎn)距離排序
    priority_queue<Node*, vector<Node*>, NodeCompare> pq;

    // 將源點(diǎn)加入隊(duì)列，并設(shè)置其距離為0
    source->distance = 0;
    pq.push(source);

    // 用于記錄已訪問過的節(jié)點(diǎn)
    unordered_map<int, bool> visited;

    while (!pq.empty()) {
        Node* currentNode = pq.top();
        pq.pop();

        // 如果節(jié)點(diǎn)已經(jīng)訪問過，跳過
        if (visited[currentNode->id]) {
            continue;
        }

        // 標(biāo)記當(dāng)前節(jié)點(diǎn)為已訪問
        visited[currentNode->id] = true;

        // 更新當(dāng)前節(jié)點(diǎn)鄰居的距離
        for (Node* neighbor : currentNode->neighbors) {
            int newDistance = currentNode->日前距離 + 1;
            if (newDistance < neighbor->distance) {
                neighbor->distance = newDistance;
                pq.push(neighbor);
            }
        }
    }
}

int main() {
    // 創(chuàng)建一些節(jié)點(diǎn)
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);

    // 構(gòu)建節(jié)點(diǎn)之間的連接關(guān)系
    node1->日前鄰居.push_back(node2);
    node1->日前鄰居.push_back(node3);
    node2->日前鄰居.push_back(node3);

    // 運(yùn)行Dijkstra算法
    dijkstra(node1);

    // 輸出節(jié)點(diǎn)到源點(diǎn)的距離
    cout << "節(jié)點(diǎn)2到源點(diǎn)的距離: " << node2->distance << endl;
    cout << "節(jié)點(diǎn)3到源點(diǎn)的距離: " << node3->distance << endl;

    return 0;
}

在這個(gè)例子里，我們先定義了Node結(jié)構(gòu)體來表示圖中的節(jié)點(diǎn)，有節(jié)點(diǎn) ID、鄰居節(jié)點(diǎn)列表和到源點(diǎn)的距離這些屬性哦。然后通過自定義的NodeCompare比較函數(shù)，讓優(yōu)先隊(duì)列按節(jié)點(diǎn)距離從小到大給節(jié)點(diǎn)排隊(duì)。接著在 Dijkstra 算法里，利用優(yōu)先隊(duì)列高效地選離源點(diǎn)最近的未訪問節(jié)點(diǎn)進(jìn)行處理，這樣就能找到從源點(diǎn)到其他節(jié)點(diǎn)的最短路徑啦。

3. 數(shù)據(jù)壓縮：讓數(shù)據(jù) “瘦身” 有妙招

在哈夫曼編碼這個(gè)數(shù)據(jù)壓縮方法里呀，優(yōu)先隊(duì)列也發(fā)揮著重要作用呢??。它就像個(gè)聰明的小助手，幫我們構(gòu)建哈夫曼樹。在構(gòu)建過程中，它會選出現(xiàn)頻率最低的兩個(gè)字符，把它們合并成一個(gè)新的 “組合字符”，然后繼續(xù)選頻率最低的進(jìn)行合并，直到構(gòu)建出完整的哈夫曼樹。最后根據(jù)這棵樹給每個(gè)字符分配不同長度的編碼，這樣就能讓數(shù)據(jù)占用更少的空間啦??。

下面是個(gè)簡單的哈夫曼編碼構(gòu)建示例，用優(yōu)先隊(duì)列來輔助構(gòu)建哈夫曼樹哦（這也是個(gè)簡化示例，實(shí)際應(yīng)用可能更復(fù)雜啦）：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 哈夫曼樹節(jié)點(diǎn)結(jié)構(gòu)體
struct HuffmanNode {
    char data;
    int frequency;
    HuffmanNode* left;
    HuffmanNode* left右;

    HuffmanNode(char d, int f) : data(d), frequency(f), left(nullptr), left右(nullptr) {}
}

// 自定義比較函數(shù)，按照節(jié)點(diǎn)頻率從小到大排序
struct HuffmanNodeCompare {
    bool operator()(const HuffmanNode* n1, const HuffmanNode* n2) {
        return n1->frequency > n2->frequency;
    }
};

// 構(gòu)建哈夫曼樹
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& frequencyMap) {
    // 創(chuàng)建優(yōu)先隊(duì)列，按照節(jié)點(diǎn)頻率排序
    priority_queue<HuffmanNode*, vector<H夫曼Node*>, HuffmanNodeCompare> pq;

    // 將每個(gè)字符及其頻率對應(yīng)的節(jié)點(diǎn)加入隊(duì)列
    for (const auto& pair : frequencyMap) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }

    while (pq.size() > 1) {
        // 取出頻率最低的兩個(gè)節(jié)點(diǎn)
        HuffmanNode* leftNode = pq.top();
        pq.pop();
        HuffmanNode* rightNode = pq.top();
        pq.pop();

        // 創(chuàng)建新的父節(jié)點(diǎn)，頻率為兩個(gè)子節(jié)點(diǎn)頻率之和
        HuffmanNode* parentNode = new HuffmanNode('\0', leftNode->frequency + rightNode->frequency);
        parentNode->left = leftNode;
        parentNode->right = rightNode;

        // 將父節(jié)點(diǎn)加入隊(duì)列
        pq.push(parentNode);
    }

    return pq.top();
}

int main() {
    // 假設(shè)這里有個(gè)字符頻率映射表
    unordered_map<char, int> frequencyMap = {
        {'a', 5},
        {'b', 3},
        {'c', 8}
    };

    // 構(gòu)建哈夫曼樹
    HuffmanNode* huffmanTree = buildHuffmanTree(frequencyMap);

    // 這里可以根據(jù)哈夫曼樹進(jìn)一步處理，比如生成編碼等，但為了簡化先不展示啦

    return 0;
}

在這個(gè)例子里，我們先定義了HuffmanNode結(jié)構(gòu)體來表示哈夫曼樹的節(jié)點(diǎn)，有字符數(shù)據(jù)、頻率、左右子節(jié)點(diǎn)這些屬性哦。然后通過自定義的HuffmanNodeCompare比較函數(shù)，讓優(yōu)先隊(duì)列按節(jié)點(diǎn)頻率從小到大給節(jié)點(diǎn)排隊(duì)。接著在構(gòu)建哈夫曼樹的過程中，利用優(yōu)先隊(duì)列選出頻率最低的兩個(gè)節(jié)點(diǎn)合并成新節(jié)點(diǎn)，一直重復(fù)這個(gè)過程直到構(gòu)建出完整的哈夫曼樹呢。

到此這篇關(guān)于C++的實(shí)現(xiàn)優(yōu)先隊(duì)列（Priority Queue）的文章就介紹到這了,更多相關(guān)C++ 優(yōu)先隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: