使用C++構(gòu)建一個優(yōu)先級隊列的實現(xiàn)
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)的文章,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-09-09VS2019創(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++中stack和queue的底層實現(xiàn)
這篇文章主要介紹了C++中的stack和dequeue的底層實現(xiàn),本文通過實例代碼給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-09-09