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

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

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

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

向上調整函數(shù)

向上調整函數(shù)就是子節(jié)點與父節(jié)點做比較，這里我們假設建小堆，如果子節(jié)點小于父節(jié)點，那么這個堆就是有問題的，所以要進行交換，將子節(jié)點與父節(jié)點進行交換，但是我們又要考慮交換以后得子節(jié)點也就是現(xiàn)在的父節(jié)點是否和他現(xiàn)在的父節(jié)點又是不對的關系的，所以我們要進行循環(huán)，只有當節(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;
        }
    }
}

向下調整函數(shù)

向下調整就是判斷你是否比你的兩個孩子都要小，邏輯和向上調整函數(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ù)

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

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

插入函數(shù)

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

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

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

我們建立這個堆或者說維護這個優(yōu)先級隊列肯定是為了得到一個有價值的元素，所有這個堆里面最有價值的元素當然時堆頂元素，但是當我們得到堆頂元素時，這個堆也會被破壞，所以，我們一般會將堆頂元素和最后一個元素進行交換，然后再對堆頂元素進行向下調整，就讓堆保持合適的規(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);
}

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

最新評論