欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

使用C++構(gòu)建一個優(yōu)先級隊列的實現(xiàn)

 更新時間:2025年02月06日 09:04:16   作者:zhoudeng666  
優(yōu)先級隊列是一種特殊的隊列數(shù)據(jù)結(jié)構(gòu),本文主要介紹了使用C++構(gòu)建一個優(yōu)先級隊列的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

1.優(yōu)先級隊列的介紹

優(yōu)先級隊列是一種特殊的隊列數(shù)據(jù)結(jié)構(gòu),它是隊列,但又不完全是,因為它要將裝載的數(shù)據(jù)進行優(yōu)先級排序,找到一個最大或者最小優(yōu)先級的元素,下一次出隊列的元素就是這個元素,所以說它不完全是一個隊列,優(yōu)先級隊列廣泛應(yīng)用于任務(wù)調(diào)度、資源分配、事件處理、Dijkstra算法、A*搜索算法等領(lǐng)域。

2.優(yōu)先級隊列的設(shè)計

 個人感覺,設(shè)計一個優(yōu)先級隊列就是一個堆建立和調(diào)整的過程,因為要裝載元素,所以我們采用vector來作為成員變量,后續(xù)就是對與這個vector變量的管理就行了,因為我們只是簡單設(shè)計一個優(yōu)先級隊列,所以并沒有設(shè)計在優(yōu)先級隊列中傳入函數(shù)進行比較的過程,只是簡單的比較大小的過程,首先我們要設(shè)計向上調(diào)整函數(shù)和向下調(diào)整函數(shù),因為這個的構(gòu)造函數(shù)和析構(gòu)函數(shù)非常簡單,這里我就不過多贅述了。

向上調(diào)整函數(shù)

向上調(diào)整函數(shù)就是子節(jié)點與父節(jié)點做比較,這里我們假設(shè)建小堆,如果子節(jié)點小于父節(jié)點,那么這個堆就是有問題的,所以要進行交換,將子節(jié)點與父節(jié)點進行交換,但是我們又要考慮交換以后得子節(jié)點也就是現(xiàn)在的父節(jié)點是否和他現(xiàn)在的父節(jié)點又是不對的關(guān)系的,所以我們要進行循環(huán),只有當(dāng)節(jié)點為0,也就是根節(jié)點或者,子節(jié)點小于父節(jié)點時,進行循環(huán)退出

void siftUp(size_t index)
{
    
    while (index > 0)
    {
        int father = index / 2;
        
        if (list[father] > list[index])
        {
            swap(list[father], list[index]);
            index = father;
        }
        else
        {
            break;
        }
    }
}

向下調(diào)整函數(shù)

向下調(diào)整就是判斷你是否比你的兩個孩子都要小,邏輯和向上調(diào)整函數(shù)差不多,只是要和兩個孩子都比一次,或者找最小的那個孩子比,主要是要知道孩子是index/2-1和index/2-2就行

void siftDown(size_t index)
{
    while (index <= list.size())
    {
        leftson = index * 2 + 1;
        rightson = index * 2 + 2;
        if (list[index] > list[leftson])
        {
            swap(list[index], list[leftson])
                index = leftson;
        }
        else if (list[index] > list[rightson])
        {
            swap(list[index], list[rightson]);
            index = rightson;
        }
        else
        {
            break;
        }
    }
}

建堆函數(shù)

在構(gòu)造函數(shù)的第一步肯定是拷貝構(gòu)造對應(yīng)的vector,然后得到的這個vector大概率不是一個堆,因此要對它進行調(diào)整,使得它可以成為一個符合規(guī)則的堆,一般建堆有兩種策略,一種是自下而上的sift down方法,另一種是自上而下的sift up方法。這里我們使用sit down 向下調(diào)整的方法,找到最后一個非葉子節(jié)點,也就是list.size()/2,然后對每個非葉子節(jié)點進行向下調(diào)整

explicit Heap(const std::vector<T>& array)
    :list(array)
{
    buildHeap();
}
void buildHeap()
{
    for (int i = list.size() / 2 ; i >=0  ; i--)
    {
        siftDown(i);
   }
}

插入函數(shù)

當(dāng)我們插入一個元素時,我們首先是尾插入vector列表,然后對這個元素進行向上調(diào)整,就使得這個堆變得規(guī)則

void insert(const T& value)
{
    list.insert(value);
    siftUp(list.size() - 1);
}

獲取頂端元素函數(shù)

我們建立這個堆或者說維護這個優(yōu)先級隊列肯定是為了得到一個有價值的元素,所有這個堆里面最有價值的元素當(dāng)然時堆頂元素,但是當(dāng)我們得到堆頂元素時,這個堆也會被破壞,所以,我們一般會將堆頂元素和最后一個元素進行交換,然后再對堆頂元素進行向下調(diào)整,就讓堆保持合適的規(guī)則

void removeTop()
{
    if (list.empty()) {
        throw std::out_of_range("Heap is empty");
    }
    swap(list[0], list[list.size() - 1]);
    siftDown(0);
    list.erase(list.end() - 1);
}

到此這篇關(guān)于使用C++構(gòu)建一個優(yōu)先級隊列的實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ 優(yōu)先級隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • c++ 數(shù)字類型和字符串類型互轉(zhuǎn)詳解

    c++ 數(shù)字類型和字符串類型互轉(zhuǎn)詳解

    今天小編就為大家分享一篇講解c++ 數(shù)字類型和字符串類型互轉(zhuǎn)的文章,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-09-09
  • 詳細了解C語言二叉樹的建立與遍歷

    詳細了解C語言二叉樹的建立與遍歷

    這篇文章主要介紹了C中二叉樹的建立和各種遍歷實例代碼,涉及樹節(jié)點的定義,后序遍歷,層序遍歷,深度優(yōu)先和廣度優(yōu)先等相關(guān)內(nèi)容,具有一定借鑒價值,需要的朋友可以參考下
    2021-07-07
  • 基于linux下獲取時間函數(shù)的詳解

    基于linux下獲取時間函數(shù)的詳解

    本篇文章是對linux下獲取時間的函數(shù)進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05
  • C++俄羅斯方塊游戲 無需圖形庫的俄羅斯方塊

    C++俄羅斯方塊游戲 無需圖形庫的俄羅斯方塊

    這篇文章主要為大家詳細介紹了無需圖形庫的C++俄羅斯方塊游戲,重溫經(jīng)典游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2016-06-06
  • 詳細分析C++ 多態(tài)和虛函數(shù)

    詳細分析C++ 多態(tài)和虛函數(shù)

    這篇文章主要介紹了C++ 多態(tài)和虛函數(shù)的相關(guān)資料,文中示例代碼非常詳細,幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-07-07
  • VS2019創(chuàng)建c++動態(tài)鏈接庫dll與調(diào)用方法實踐

    VS2019創(chuàng)建c++動態(tài)鏈接庫dll與調(diào)用方法實踐

    動態(tài)鏈接庫是一個包含可由多個程序同時使用的代碼和數(shù)據(jù)的庫,本文主要介紹了VS2019創(chuàng)建c++動態(tài)鏈接庫dll與調(diào)用方法,具有一定的參考價值,感興趣的可以了解一下
    2024-06-06
  • 基于C語言實現(xiàn)三子棋游戲

    基于C語言實現(xiàn)三子棋游戲

    這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)三子棋游戲,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-08-08
  • 詳解C++中函數(shù)模板的定義與使用

    詳解C++中函數(shù)模板的定義與使用

    函數(shù)模板實質(zhì)就是參數(shù)化數(shù)據(jù)類型,稱這種編程模式為數(shù)據(jù)類型泛化編程。本文將通過示例來和大家一起了解下C++中函數(shù)模板的定義與使用,需要的可以參考一下
    2022-09-09
  • 深入探索C++中stack和queue的底層實現(xiàn)

    深入探索C++中stack和queue的底層實現(xiàn)

    這篇文章主要介紹了C++中的stack和dequeue的底層實現(xiàn),本文通過實例代碼給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-09-09
  • 淺談C語言中的指針和數(shù)組有什么區(qū)別

    淺談C語言中的指針和數(shù)組有什么區(qū)別

    C語言中的指針和數(shù)組是兩個重要的數(shù)據(jù)結(jié)構(gòu),它們在內(nèi)存管理和數(shù)據(jù)存儲方面有許多相似之處,但也存在一些關(guān)鍵的區(qū)別,本文就來介紹一下C語言中的指針和數(shù)組有什么區(qū)別,具有一定的參考價值,感興趣的可以了解一下
    2023-09-09

最新評論