1.優(yōu)先級(jí)隊(duì)列的介紹

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

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

 個(gè)人感覺(jué)，設(shè)計(jì)一個(gè)優(yōu)先級(jí)隊(duì)列就是一個(gè)堆建立和調(diào)整的過(guò)程，因?yàn)橐b載元素，所以我們采用vector來(lái)作為成員變量，后續(xù)就是對(duì)與這個(gè)vector變量的管理就行了，因?yàn)槲覀冎皇呛?jiǎn)單設(shè)計(jì)一個(gè)優(yōu)先級(jí)隊(duì)列，所以并沒(méi)有設(shè)計(jì)在優(yōu)先級(jí)隊(duì)列中傳入函數(shù)進(jìn)行比較的過(guò)程，只是簡(jiǎn)單的比較大小的過(guò)程，首先我們要設(shè)計(jì)向上調(diào)整函數(shù)和向下調(diào)整函數(shù)，因?yàn)檫@個(gè)的構(gòu)造函數(shù)和析構(gòu)函數(shù)非常簡(jiǎn)單，這里我就不過(guò)多贅述了。

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

向上調(diào)整函數(shù)就是子節(jié)點(diǎn)與父節(jié)點(diǎn)做比較，這里我們假設(shè)建小堆，如果子節(jié)點(diǎn)小于父節(jié)點(diǎn)，那么這個(gè)堆就是有問(wèn)題的，所以要進(jìn)行交換，將子節(jié)點(diǎn)與父節(jié)點(diǎn)進(jìn)行交換，但是我們又要考慮交換以后得子節(jié)點(diǎn)也就是現(xiàn)在的父節(jié)點(diǎn)是否和他現(xiàn)在的父節(jié)點(diǎn)又是不對(duì)的關(guān)系的，所以我們要進(jìn)行循環(huán)，只有當(dāng)節(jié)點(diǎn)為0，也就是根節(jié)點(diǎn)或者，子節(jié)點(diǎn)小于父節(jié)點(diǎn)時(shí)，進(jìn)行循環(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)整就是判斷你是否比你的兩個(gè)孩子都要小，邏輯和向上調(diào)整函數(shù)差不多，只是要和兩個(gè)孩子都比一次，或者找最小的那個(gè)孩子比，主要是要知道孩子是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)造對(duì)應(yīng)的vector，然后得到的這個(gè)vector大概率不是一個(gè)堆，因此要對(duì)它進(jìn)行調(diào)整，使得它可以成為一個(gè)符合規(guī)則的堆，一般建堆有兩種策略，一種是自下而上的sift down方法，另一種是自上而下的sift up方法。這里我們使用sit down 向下調(diào)整的方法，找到最后一個(gè)非葉子節(jié)點(diǎn)，也就是list.size()/2,然后對(duì)每個(gè)非葉子節(jié)點(diǎn)進(jìn)行向下調(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)我們插入一個(gè)元素時(shí)，我們首先是尾插入vector列表，然后對(duì)這個(gè)元素進(jìn)行向上調(diào)整，就使得這個(gè)堆變得規(guī)則

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

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

我們建立這個(gè)堆或者說(shuō)維護(hù)這個(gè)優(yōu)先級(jí)隊(duì)列肯定是為了得到一個(gè)有價(jià)值的元素，所有這個(gè)堆里面最有價(jià)值的元素當(dāng)然時(shí)堆頂元素，但是當(dāng)我們得到堆頂元素時(shí)，這個(gè)堆也會(huì)被破壞，所以，我們一般會(huì)將堆頂元素和最后一個(gè)元素進(jìn)行交換，然后再對(duì)堆頂元素進(jìn)行向下調(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)建一個(gè)優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ 優(yōu)先級(jí)隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論