優(yōu)先隊(duì)列的基本概念

在計(jì)算機(jī)科學(xué)中，優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型，它與隊(duì)列相似，但是每個(gè)元素都有一個(gè)相關(guān)的優(yōu)先級(jí)。在優(yōu)先隊(duì)列中，當(dāng)我們執(zhí)行插入操作時(shí)，我們將元素插入到隊(duì)列中，并根據(jù)其優(yōu)先級(jí)對其進(jìn)行排序。在刪除操作中，我們會(huì)刪除優(yōu)先級(jí)最高的元素，并把隊(duì)列進(jìn)行重新排序。優(yōu)先隊(duì)列通常使用堆來實(shí)現(xiàn)。

C++中的優(yōu)先隊(duì)列是一個(gè)容器適配器(container adapter)，它提供了一種在元素之間維護(hù)優(yōu)先級(jí)的方法。使用C++優(yōu)先隊(duì)列，你可以在隊(duì)列頭部添加新元素，并從隊(duì)列頭部移除元素。當(dāng)添加元素時(shí)，它將根據(jù)元素的排序準(zhǔn)則將其放置在適當(dāng)?shù)奈恢谩?/p>

優(yōu)先隊(duì)列的使用方法

在C++中，我們可以使用頭文件"queue"中的priority_queue來創(chuàng)建一個(gè)優(yōu)先隊(duì)列。接下來是一個(gè)簡單的代碼示例，它說明了如何使用priority_queue創(chuàng)建一個(gè)整數(shù)類型的隊(duì)列。

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(1);
    pq.push(2);
    pq.push(3);
    
    std::cout << "Queue Size : " << pq.size() << std::endl;
    std::cout << "Top Element: " << pq.top() << std::endl;

    while(!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }
    return 0;
}

在上面的代碼中，我們首先包含頭文件"queue"，并使用std::priority_queue來創(chuàng)建一個(gè)整數(shù)類型的優(yōu)先隊(duì)列。接下來，我們使用push()方法向隊(duì)列中添加元素。在添加元素后，我們可以使用size()方法來檢查隊(duì)列的大小。我們還可以使用top()方法獲取隊(duì)列的頂部元素。

在while循環(huán)中，我們使用top()方法檢查頂部元素，并使用pop()方法從隊(duì)列中刪除它。

優(yōu)先隊(duì)列元素的排序規(guī)則

默認(rèn)情況下，C++優(yōu)先隊(duì)列使用std::less來確定哪個(gè)元素具有更高的優(yōu)先級(jí)。這意味著優(yōu)先隊(duì)列中的元素以升序排列。如果您想使用降序排列，您可以將std::greater用作參數(shù)。

接下來是一個(gè)降序排列的示例：

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(3);
    pq.push(2);
    pq.push(1);
    
    std::cout << "Queue Size : " << pq.size() << std::endl;
    std::cout << "Top Element: " << pq.top() << std::endl;

    while(!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }
    return 0;
}

在上述代碼中，我們向priority_queue的構(gòu)造函數(shù)中添加了第三個(gè)參數(shù)std::greater。這表示我們正在使用降序排列。

元素的自定義排序

有時(shí)，您可能需要使用自定義排序規(guī)則將元素插入到C++優(yōu)先隊(duì)列中。在這種情況下，您可以使用lambda表達(dá)式或者實(shí)現(xiàn)一個(gè)二元謂詞(類似于比較函數(shù))。

接下來是一個(gè)使用lambda表達(dá)式進(jìn)行排序的示例：

#include <iostream>
#include <queue>

struct custom_struct {
    int priority;
    std::string message;

    custom_struct(int priority_, std::string message_) : priority(priority_), message(message_) {}
};

int main() {
    auto comp = [](custom_struct a, custom_struct b) {return a.priority > b.priority;};
    std::priority_queue<custom_struct, std::vector<custom_struct>, decltype(comp)> pq(comp);

    pq.push(custom_struct(1, "Hello"));
    pq.push(custom_struct(2, "World"));
    pq.push(custom_struct(3, "Priority"));
    
    std::cout << "Queue Size : " << pq.size() << std::endl;
    std::cout << "Top Element: " << pq.top().message << std::endl;

    while(!pq.empty()) {
        std::cout << pq.top().message << std::endl;
        pq.pop();
    }
    return 0;
}

在上述代碼中，我們首先定義一個(gè)名為custom_struct的自定義結(jié)構(gòu)體。接下來，我們使用lambda表達(dá)式定義了一個(gè)比較二元謂詞。第三個(gè)參數(shù)是我們自定義的二元謂詞。最后，我們創(chuàng)建了一個(gè)custom_struct類型的優(yōu)先隊(duì)列，并在其構(gòu)造函數(shù)中使用comp參數(shù)，這將使用我們剛剛定義的比較謂詞對元素進(jìn)行排序。

優(yōu)先隊(duì)列的時(shí)間復(fù)雜度

C++優(yōu)先隊(duì)列是使用堆來實(shí)現(xiàn)的。插入和刪除元素的時(shí)間復(fù)雜度為O(log(n))，其中n是隊(duì)列中的元素?cái)?shù)。獲取隊(duì)列頂部元素的時(shí)間復(fù)雜度為O(1)。由于我們使用的是標(biāo)準(zhǔn)容器庫，所以這些時(shí)間復(fù)雜度是可以保證的。

總結(jié)

C++優(yōu)先隊(duì)列是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它允許我們以有序的方式存儲(chǔ)和訪問元素。無論是從插入元素的角度還是從獲取頂端元素的角度來看，使用C++優(yōu)先隊(duì)列都比自己手動(dòng)實(shí)現(xiàn)堆或者排序數(shù)組更加快速和便捷。掌握C++優(yōu)先隊(duì)列可以讓您更輕松地完成許多常見的編程任務(wù)，并且可以提高您的編碼效率和代碼質(zhì)量。

到此這篇關(guān)于深入了解C++優(yōu)先隊(duì)列(priority_queue)的使用方法的文章就介紹到這了,更多相關(guān)C++ 優(yōu)先隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論