🔥 本文專欄:c++
🌸作者主頁:努力努力再努力wz
💪 今日博客勵志語錄:
真正的強大,不是從不跌倒,而是每次跌倒后都能笑著站起來
★★★ 本文前置知識:
模版
引入
那么priority_queue便是我們c++的stl庫中的又一個容器,那么它便是我們是熟知的優先級隊列,那么我們就可以從該容器的名字看出它的特點,那么它在隊列的基礎上加了一個優先級來修飾,我們知道隊列是一個先進先出的數據結構,那么所謂的優先級則決定了哪些在隊列中的元素誰能夠在隊列的前方,意味著該元素的優先級高,那么它就會率先彈出該隊列,而優先級低的,則只能在隊列的尾部,那么它就不會被率先被彈出隊列,那么這個優先級則是可以由我們用戶自己定義。
那么知道了優先級隊列的一個概念之后,那么接下來讀者關心的第一個問題,肯定就是優先級隊列底層結構是什么,也就是采取的是什么方式來實現優先級隊列的呢?那么估計有一部分讀者想當然的就認為優先級隊列采取就是用隊列來實現,那么根據自己前面學習棧和隊列容器的經驗,那么這里優先級隊列的實現可以采取容器適配器模式,里面定義一個隊列,然后復用隊列的成員函數即可了,但是事實上,c++的stl的設計者底層并沒有采取隊列來實現,而是采取的是堆這個結構,那么人家采取堆而不是隊列肯定有自己的原因,那么這個原因是什么我會在后文提到,那么在知道這個原因之前,那么首先我們就得知道什么是堆結構,所以本文的第一部分內容,便是回顧與講解堆,那么我相信有的讀者對這個結構是十分熟悉,如果熟悉的話,那么就可以跳過這部分內容,如果不熟悉感到有些陌生的讀者,那么可以看看這部分內容,幫組你回憶一下堆結構,而優先級隊列的實現關鍵就是堆
堆
什么是堆
那么堆這個名字一聽,很多初學者會以為它是繼順序表和鏈表以及棧和樹等等數據結構之后又一個新的數據結構,但其實堆本質就是一棵二叉樹,那么為什么把這棵二叉樹給稱之為堆呢,那么是因為這棵二叉樹不僅能夠存儲數據,而且其最大的作用是可以對樹中的所有的節點進行排序,所以這個堆就是一棵特殊的二叉樹,那么要能做到排序,那么堆就必須滿足一個性質,那么就是根節點必須大于或者等于它的左右孩子節點,并且遞歸的對于左右子樹來說,也得同樣滿足其根節點大于或者等于其孩子節點,那么我們發現如果該二叉樹滿足該性質之后,此時對于該整個二叉樹的根節點來說,其便有了意義,那么該二叉樹的根節點是該二叉樹中所有節點中元素最大的一個節點,那么該根節點也被稱之為堆頂,那么說到這里,那么想必讀者就能知道堆排序的原理了,由于堆頂是整個元素最大的,那么接下來我要做的就是刪除堆頂元素,然后對除了堆頂的剩余的所有元素再來建堆,那么此時由剩余節點再來組成一棵滿足堆性質的完整的二叉樹,那么該二叉樹中根節點是最大的,那么此時我們就只需獲取根節點的元素值從而找到次大的元素,那么該二叉樹也稱之為大根堆,因為堆頂是整個堆中所有元素最大的,那么既然有大根堆,那么肯定就要小根堆,那么小根堆就是滿足根節點小于或者等于其左右孩子,并且遞歸的左右子樹都得滿足該性質,那么此時對于小根堆來說,那么其堆頂就是該堆最小的元素
那么知道了堆排序大致的原理之后,那么有的讀者可能此時糾結于某個具體的操作等細節,比如怎么刪除堆頂以及刪除完之后這個建堆又怎么實現,那么先別急著關注這些,那么我們先循序漸進,那么通過上文的講述,你知道了堆的概念也就是什么是堆,那么它是一棵滿足特殊性質的二叉樹,那么接下來的關注點就是如何實現構建這棵二叉樹,那么我們知道二叉樹有兩種方式實現,第一種就是定義一個二叉樹的節點,那么每一個節點分別有兩個指針域,指向其對應的左右孩子,還有一個數據域來存儲數據,那么第二種方式就是通過數組來實現,那么這兩種方式都能夠實現構造一棵二叉樹,但是具體選擇哪一個,那么我們得講解建堆操作之后,那么讀者自然才能明白體會到選擇哪個實現方式更合理和優秀,這里就先埋一個伏筆。
建堆
那么使用堆的需求肯定就是我們要對一個區間的數據進行排序,那么我們第一步要做的就是將這個區間中的數據給構造成一個滿足堆性質的二叉樹,那么此時就需要我們進行建堆操作,那么建堆的方式有兩種,那么分別是向上調整建堆和向下調整建堆,那么首先我先來講解一下向上調整建堆
1.向上調整建堆
原理
那么向上調整建堆的核心思想就是從上往下依次構建出滿足堆性質的二叉樹,那么所謂的從上往下就是從根節點開始依次往下構建二叉樹,那么此時我們可以理解為我們的滿足堆性質的二叉樹的初始狀態是一棵空樹,也就是沒有任何節點,那么此時我們再將要排序區間里面的數據依次插入到該樹中,那么每一次新插入的位置都是從當前這棵二叉樹的最后一層的最后一個葉子節點位置的右側第一個葉子節點處(如果該最后一個葉子節點是該層的最右側節點,那么新插入的位置則是下一層第一個),因為我們是從上往下從左往右依次添加節點,那么每次新插入的位置就是該二叉樹最后一個葉子節的右側,所以按照這種插入方式,那么堆的本質就是一棵完全二叉樹,那么我們將數據成功插入到該二叉樹中還并沒有結束,因為我們該二叉樹要滿足堆性質,也就是根節點要大于或者等于左右孩子節點,那么此時你雖然你添加了一個葉子節點,但是添加玩之后不能破壞二叉樹的堆性質,比如你這個新添加的葉子節點可能會大于根節點(以大根堆為例),那么此時你插入完之后的下一步就是調整新插入的節點的位置,那么如果它大于根節點,就與根節點的值進行交換,然后依次與沿途的祖先節點比較,直到不大于根節點結束,這就是所謂的向上調整
那么肯定會有讀者會思考向上調整這種方式為什么是正確?
那么由于我們每次在插入節點之前,那么該二叉樹是滿足堆性質,也就是根節點大于等于左右孩子節點,那么我們知道此時新插入的節點的父節點一定是大于等于它的兄弟節點(如果新插入的節點是右孩子),那么如果它大于父節點,那么意味著它一定大于它的兄弟節點,所以新插入的節點與根節點交換之后的結果是滿足堆性質,即交換之后滿足根節點大于或者等于左右孩子節點,那么它同理可以重復同樣的方式與沿途的祖先節點比較,那么沿途被換下來的祖先節點也一定是大于等于它左右子樹中的所有節點的,所以能保證該沿途下的節點都滿足堆性質,并且新插入的節點只和沿途節點比較,那么其他分支的節點不會受到影響,而我們說過在插入節點之前,那么二叉樹已經滿足堆性質,所以調整結束后,整個二叉樹就滿足堆性質
所以根據我們上文的分析,我們就知道能夠向上調整的前提一定是你節點插入之前,該二叉樹一定是滿足堆性質的,如果該二叉樹不滿足堆性質,那么你的調整是沒有意義的,你與根節點比較,那么根節點都可能小于的的兄弟節點,你與其交換也沒有任何用
那么這里我們就可以解決上文沒談到埋的那個伏筆了,也就是選擇哪種方式構建二叉樹,是鏈表還是數組,那么這里我們根據采取向上調整建堆的原理,我們就可以知道,那么每次對新插入的節點向上調整的過程,都需要與沿途的父節點進行比較,那么如果你采取的是鏈表的方式,此時你的每一個節點光有兩個指向左右孩子節點的指針還不夠,還得添加一個指向父節點的指針,其次我們上文也說到,每次插入的節點都是該二叉樹的最后一個葉子節點的右側因為我們是從上往下從左往右依次插入,那么此時你還得每次都遍歷一遍二叉樹獲取到當前最后一個葉子節點然后插入再去調整,那么這就是采取鏈表實現向上調整的建堆方式,那么剛才的這種方式絕對沒錯,肯定能夠實現,但是缺陷也太明顯了,那就是太復雜并且效率太低
那么第二種方式是數組,那么首先我們是如何通過這個數組這個連續的物理結果映射到二叉樹這個邏輯結構上呢,那么就是通過數組的下標,那么我們為該二叉樹中的每一個節點編號,從根節點開始從上往下從左往右依次給編號為1開始往后,那么根節點和左右孩子節點的索引就滿足一個公式:
假設根節點編號為i
左孩子節點索引=2i+1左孩子節點索引=2i+1 左孩子節點索引=2i+1
右孩子節點索引=2i+2右孩子節點索引=2i+2 右孩子節點索引=2i+2
假設已知左孩子索引為k1,右孩子索引為k2:
父節點索引=(k1?1)/2父節點索引=(k1-1)/2 父節點索引=(k1?1)/2
父節點索引=(k2?1)/2父節點索引=(k2-1)/2 父節點索引=(k2?1)/2
那么這個公式的證明你可以自己觀察枚舉來證明,通俗點來說,就是自己畫一個二叉樹自己隨便算一下,發現根節點與左右孩子一定是滿足該公式,嚴格一點,你可以通過數學歸納法來證明,這里我就不再講述該證明方式了
所以根據這個公式,那么數組的下標就能夠描述二叉樹的父子節點關系從而建立邏輯映射,而堆本質是一棵完全二叉樹,那么堆中的節點在數組中是連續存放的,那么數組的空間利用率就很高,而根據上文的向上調整建堆的原理,而數組由于可以通過下標隨機訪問的特性,那么我們就可以通過子節點的編號來計算父節點,然后比較,更為關鍵的是,每次新插入的節點就是該數組的有效數據的末尾,因為從左往右依次插入,那么我們只需維護一個變量size就能得到數組有效數據的末尾的下標,無序遍歷,所以采取數組實現是更為合理和高效
實現
那么關于向上調整的實現,有的小伙伴想用遞歸因為該二叉樹結構,其實這里直接用循環即可,不用遞歸,那么循環的終止條件就是如果此時你的新插入的節點都被調到根節點(堆頂)了,那么根節點上面都沒有節點了也就是新插入的節點的下標等于0,你就沒必要調了直接退出循環,或者說你向上調整的過程中,此時被調整的該節點你小于等于了根節點(以大根堆為例),那么意味著此時整個二叉樹都滿足堆性質,那么也沒有必要調直接退出循環,那么如果大于的話,那么此時就交換根節點與該節點的值,然后該節點此時就作為根節點,然后進入下一次循環與每次按照公式計算出它的父親節點然后比較比較
void adjustUp(vector<datatype>& l1,size_t child)//這是大堆的向上調整,小堆的話就改下比較邏輯即可
{size_t parent = (child - 1) / 2;while (child > 0){if (l1[child] > l1[parent]){std::swap(l1[child], l1[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
2.向下調整建堆
原理
那么向上調整建堆,就是從頂到底依次構建我們的滿足堆性質的二叉樹,那么向下調整顧名思義就是從底到頂構建我們的二叉樹,那么還是一樣,我們還是有一個要排序區間的數據,那么我們先把他們放到一個數組當中,意味著這些數據整體構成了一棵二叉樹,但是此時這棵二叉樹是不滿足堆性質的,必定需要經過調整
向上調整建堆的前提就是插入節點之前,該二叉樹已經滿足堆性質,而對于向下調整,那么其也要滿足一個前提,那么就是被調整的位置肯定是二叉樹中的某個節點,那么該前提就是該節點的左右子樹必須得滿足堆性質,才可以對該位置向下調整建堆,因為向下調整建堆的原理,就是該節點與其左右孩子節點中較大的比較,如果它小于較大的孩子節點(以大堆為例),那么就與該孩子節點的較大值交換,然后依次沿途往下比較,直到調整到正確位置,如果左右子樹不滿足堆性質,那么意味著至少有一個子樹不滿足堆性質,那么假設你交換到其中一個子樹中去,而另一個子樹已經不滿足堆性質,那么你交換也沒用,所以必須滿足該前提
那么為什么向下調整建堆這種交換式正確的呢?
那么由于我們得到較大孩子,如果較大孩子比該根節點大,那么我們可以放心交換,那么交換后,新的根節點一定大于左右孩子,那么一定是滿足堆性質,所以這種交換是正確的
其次就是為什么我們從倒數第二次開始調整,就是因為向下調整的前提條件要求其左右子樹滿足堆性質,而倒數第一層的左右子樹都為空,那么左右子樹都為空可以理解為左右子樹都是無窮小,那么倒數第一層天然滿足堆性質,那么我們直接從倒數第二層開始調整,那么到時第二層都滿足對性質之后,那么我們就可以調整倒數第三層依次往上,最終構建一個整體的堆
實現
那么這里現在我們持有一個數組下標,對應某個需要向下調整的節點,那么它的左右子樹已經滿足堆性質,那么接下來我們就先得到較大孩子,然后比較該節點與較大孩子的大小,然后如果其小于較大孩子,那么就交換,此時的節點的位置就到了給較大孩子的位置,然后進入下一次循環,每次循環會計算出左孩子和右孩子節點,然后得到較大孩子,然后比較,一旦調整到最底部或者根節點大于等于較大孩子節點,就不需要調整,直接退出循環
void adjustDown(vetcor<datatype>& l1,size_t parent)//這里是大根堆的向下調整,小根堆的向下調整只需修改比較邏輯即可
{size_t child = parent * 2 + 1;while (child < l1.size()){int fit_child = child;if (child + 1 < l1.size() &&l1[child+1]>l1[child])){fit_child= child + 1;}if (l1[fit_child]>l1[parent]){std::swap(_con[parent], _con[fit_child]);parent = fit_child;child = 2 * parent + 1;}else{break;}}
}
3.兩種建堆方式的效率比較
那么這里我們既可以才起向上調整建堆,那么也可以采取向下調整建堆,那么這兩種方式究竟誰效率更高了,那么就需要我們來比較一下這兩種方式的一個時間復雜度,那么我們就得估算一下這兩種方式的時間復雜度,那么我們就以最壞時間復雜度來衡量,那么假設這里我們有高度為h層的滿二叉樹,那么我們先來估計向下調整建堆的時間復雜度:
那么向下調整建堆是從倒數第二層開始調整,那么由于是估計最壞的時間復雜度,那么從倒數第二層往上,那么每一層的節點就是都調整最底部,那么由于是滿二叉樹,那么第i層的節點的個數就是2^(i-1),那么其往下調整的高度就是h-i,那么我們計算出每一層的總調整次數,也就是每層的結點個數乘向下的高度,然后累加每一層的總調整個數個數,最后來估算時間復雜度:
T(N)=2h?2?1+2h?3?2+2h?3?3+.....+22?(h?3)+21?h?2+20?(h?1)T(N)=2^{h-2}* 1+2^{h-3}*2+2^{h-3}*3+ .....+2^{2}*(h-3)+2^{1}*h-2+2^{0}*(h-1) T(N)=2h?2?1+2h?3?2+2h?3?3+.....+22?(h?3)+21?h?2+20?(h?1)
那么我們觀察該數列,那么是一個等差乘以等比數列,那么可以采取錯位相乘法,也就是整體乘以2,然后再錯位相減
2?T(N)=2h?1?1+2h?2?2+2h?2?3+.....+22?h+21?(h?1)2*T(N)=2^{h-1}*1+2^{h-2}*2+2^{h-2}*3+.....+2^{2}*h+2^{1}*(h-1) 2?T(N)=2h?1?1+2h?2?2+2h?2?3+.....+22?h+21?(h?1)
T(N)=2h?2?1+2h?3?2+2h?3?3+.....+22?(h?3)+21?h?2+20?(h?1)T(N)=2^{h-2}* 1+2^{h-3}*2+2^{h-3}*3+ .....+2^{2}*(h-3)+2^{1}*h-2+2^{0}*(h-1) T(N)=2h?2?1+2h?3?2+2h?3?3+.....+22?(h?3)+21?h?2+20?(h?1)
然后兩個等式相減,然后中間重合部分就是一個等比數列,那么就可以利用等比數列求和公式,最終再根據h=logN,然后得到估計出向下建堆的時間復雜度是O(N)級別的
那么對于向上建堆,這里和向下建堆的估算方法是一樣的,同樣也會用到錯位相減法,那么最終估算出來其時間復雜度是O(N*logN)
那么對于向下調整和向上調整,其實我們可以通過觀察就可以粗略的估計出兩種方式誰更優秀,因為二叉樹越靠近底部的節點的數量更多,那么向下調整對于底部節點來說其調整的次數是很小的,因為其靠近底部,但是對于向上調整來說,底部的大量元素會涉及沿途調整較多的次數,所以向下調整是更優秀的
刪除
原理
那么這里對于堆的刪除來說,那么堆的刪除不能像數組或者鏈表那樣,支持任意位置刪除,因為由于堆這個結構本身的特殊性,那么堆頂的元素便具有了意義,那么堆頂的元素代表著該二叉樹的最大或者最小的元素,所以堆的刪除則是只能刪除堆頂,而對于堆的刪除來說,那么它刪除的目的不是為了舍棄這個元素,而是為了獲取到最值,而上文我們說過,堆是用數組來實現的,那么是通過數組下標來建立與二叉樹的邏輯映射,那么對于有些讀者,那么他知道堆頂元素就是對應數組的第一個位置,那么他采取的做法就是直接挪動元素來刪除堆頂的元素,將之后的元素整體向前挪動一個單位
那么我們首先評價一下這種方式,那么數組是通過下標來表示二叉樹節點之間的父子關系,那么如果你直接暴力移動,那么就會導致二叉樹的節點之間的父子關系混亂,同時也會破壞堆的性質,那么有的讀者就會抬杠,他舉得這里移動確實會破壞堆結構,那么你移動完之后,在對移動后的所有元素再重新建堆,然后再獲取堆頂不就可以了嗎
那么這種方式肯定是正確,沒有任何問題的,但是缺陷就在效率上,那么這里涉及到了挪動元素,那么注定這個方式的效率是不夠優秀
那么這里我們注意,刪除了堆頂的元素,而由堆結構我們可以知道,堆的左右子樹依然都滿足堆性質,那么這里我們就可以利用左右子樹的堆性質,而上文說的向下調整就需要左右子樹滿足堆性質,所以這里我們更為優秀的做法就是這里堆頂與最后一個葉子節點的值進行交換,那么此時由于我們是數組來實現,到時候我們會維護一個size變量來記錄有效長度,然后size–,那么此時現在處于有效數據末尾的堆頂就被邏輯上的刪除了,而此時原本處于末尾,而現在被交換到堆頂的元素,就會導致整個二叉樹是肯定是不滿足堆結構的,那么我們就從堆頂開始向下調整就完了,因為除了堆頂,它的左右子樹都滿足堆性質,那么這就是我們刪除的一個原理
實現
那么刪除的實現就首先交換元素,然后對堆頂位置向下調整就可以了
void pop(vector<datatype>& l1){std::swap(l1[0], l1[l1.size() - 1]);adjustDown(l1,0);l1.resize(l1.size() - 1);}
堆排序
那么接下來就是講解如何用堆進行排序了,我們知道堆有大根堆以及小根堆兩種,所以堆排序的第一個環節就是選擇哪個堆來實現,那么假設我們要給一個數組中的元素排一個降序,那么我們究竟選擇什么堆
那么有的讀者自然想到建大堆,因為堆頂為最大元素,獲取完堆頂元素后再刪除,再建堆在取次大的,那么這個方式可以是可以,那么關鍵是你得額外開辟一個數組,從前往后放依次放取下的堆頂,那么有沒有一種更優秀的方式,也就是不需要額外的數組,直接在原數組的基礎上進行排序
能實現原數組的基礎上進行排序只能是建小堆,雖然小堆是獲取當前最小元素,但是根據我們堆的刪除的原理,那么堆頂的元素會與最后一個葉子節點進行交換,那么此時刪除過后,那么最小的元素就在最后面,那么接著在對原數組的元素再向下調整建堆,那么重復剛才的操作,那么就能夠得到次小然后緊跟在剛才最小數的前面,最終就能得到降序并且還是是在原數組的基礎上,不需要額外開辟空間
而同理升序就要建大堆,那么原理就和上面一樣,不在多說,那么這里我們再來評估一下堆排序的時間復雜度,那么每次向下調整的時間復雜度是O(logN),那么總共要有n次,所以堆排的時間復雜度是o(n*logN),那么這就是關于堆的所有的內容,那么帶你全方位回顧了堆
優先級隊列
那么再知道了堆這個結構之后,那么這里為什么優先級隊列選擇用堆實現而不是隊列,那么因為堆的性質,那么我們可以在向上以及向下調整中自定義一種比較方式,那么讓優先級最高的元素處于堆頂,而對于隊列來說,那么你根據優先級調整隊列中的位置,那么想必只能一個一個數之間依次比較,那么時間復雜度是o(N^2)才能得到一個優先級隊列,而堆的話,根據上文所說的向下調整建堆,只需要O(N),所以這就是為什么選擇堆作為優先級隊列的底層實現
那么堆是采取數組實現,那么有了之前棧和隊列的經驗,那么這里我們就只需要利用適配器模式,利用已有的vector,不用我們再自己開辟維護動態數組了,那么對于優先級隊列的各種成員函數就是復用已有的容器的成員函數,實現很簡單,沒必要拿出來再細講了,能提的就是push與pop成員函數
push函數
那么push函數的實現要用到向上調整建堆而無法用向下調整建堆,因為在插入之前,優先級隊列可能已經有元素了并且其一定滿足堆性質,那么直接就是利用向上調整即可,無法向下,因為插入的位置都是位于最后一層,那么上文講解向下調整原理時說過,向下調整只能從倒數第二層開始
void push(const T& val){_con.push_back(val);adjustUp(_con.size()- 1);}
pop函數
那么pop函數就是交換元素,然后向下調整即可
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);adjustDown(0);_con.resize(_con.size() - 1);
}
而這里優先級隊列真正要講的就是這里的仿函數,那么仿函數是我們優先級隊列實現的重點
仿函數
那么我們知道堆有大堆和小堆,那么這里我們創建一個優先級隊列,那么有可能建的是大堆也有可能建的是小堆,那么如何實現一個能夠同時支持這兩個堆的優先級隊列呢,那么有的讀者想的就是定義兩個模板類,分別一個支持大堆,另一個支持小堆,然后再把這兩個模板類封裝到一起即可,那么這樣肯定是可行的,但是我們發現大堆和小堆的核心的代碼邏輯不同就在于向上以及向下調整建堆時候父子節點的比較,那么這里我們就可以采取仿函數,那么所謂的仿函數就是在一個類中重載()運算符,那么我們創建一個類的對象,然后調用該運算符重載函數即可,那么這就是所謂的仿函數,其實就是調用一個類的()重載函數,而仿函數名稱的由來則就是其調用該運算符重載函數很像調用一個普通函數而不是調用類的成員函數
class node
{int operator()(int x,int y){return x+y;}
};
int main()
{node add;int x=10;int y=20;cout<<add(10,20)<<endl; //你的視角//編譯器的視角 :add.operator()(x,y)return 0;
}
但是由于我們不知道優先級隊列中存儲的數據類型具體是什么樣,所以這里就只能將仿函數定義為模板類,然后根據到時候傳進來的參數實例化出相應的類,所以你可以看到優先級隊列的第三個模版參數是一個仿函數,那么其默認是less,也就是大堆
template<typename T>
class less
{
public:bool operator()(const T& l1, const T& l2){return l1 > l2;}
};
template<typename T>
class greater
{
public:bool operator()(const T& l1, const T& l2){return l1 < l2;}
};
template<typename T,typename container=std::vector<T>,typename com=less<T>>
class prioriety_queue
{private:container _con;
};
所以這里的向上調整以及向下調整就需要建立一個仿函數對象compare,然后再調用()運算符重載函數
源碼
priority_queue.h
#pragma once
#include<vector>
#include<algorithm>
namespace wz
{template<typename T>class less{public:bool operator()(const T& l1, const T& l2){return l1 > l2;}};template<typename T>class greater{public:bool operator()(const T& l1, const T& l2){return l1 < l2;}};template<typename T,typename container=std::vector<T>,typename com=less<T>>class prioriety_queue{private:container _con;public:void adjustDown(size_t parent){com compare;size_t child = parent * 2 + 1;while (child < _con.size()){int fit_child = child;if (child + 1 < _con.size() &&compare(_con[child+1],_con[child])){fit_child= child + 1;}if (compare(_con[fit_child] , _con[parent])){std::swap(_con[parent], _con[fit_child]);parent = fit_child;child = 2 * parent + 1;}else{break;}}}void adjustUp(size_t child){com compare;size_t parent = (child - 1) / 2;while (child > 0){if (compare(_con[child] , _con[parent])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& val){_con.push_back(val);adjustUp(_con.size()- 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);adjustDown(0);_con.resize(_con.size() - 1);}const T& top(){return _con[0];}bool empty() {return _con.empty();}size_t size() const{return _con.size();}};
}
priority_queue.cpp:
#include"prioriety_queue.h"
#include<iostream>
using std::cout;
using std::endl;
int main()
{wz::prioriety_queue<int> l1;l1.push(2);l1.push(5);l1.push(4);l1.push(9);l1.push(20);l1.push(1);l1.push(2);while (!l1.empty()){cout << l1.top() <<" ";l1.pop();}return 0;
}
運行截圖:
結語
那么這就是本文的全部內容,那么介紹了堆以及優先級隊列,其中還引出了仿函數,那么希望下來讀者也可以自己模擬實現一下優先級隊列,能夠加深你對優先級隊列的理解,那么下一期文章我將更新模版,希望你能持續關注,如果本文對你有幫組的話,還請三連加關注哦,你的支持,就是我創作最大的動力!