本項(xiàng)目GitHub： HuangCheng72/HCSTL: 我的STL實(shí)現(xiàn) (github.com): https://github.com/HuangCheng72/HCSTL

進(jìn)入正文。

在上一篇中，我們已經(jīng)給 vector 和 list 完成了迭代器的部分，現(xiàn)在我們的這兩個(gè)容器可以通過迭代器操作容器里面的數(shù)據(jù)了，現(xiàn)在我們可以實(shí)際地應(yīng)用這兩個(gè)容器了，我們以 vector 為例。

優(yōu)先隊(duì)列（Priority Queue）是一種常用的數(shù)據(jù)結(jié)構(gòu)，每次取出的元素都是隊(duì)列的全部元素中具有最高優(yōu)先級的元素（具體視排序規(guī)則而定），優(yōu)先隊(duì)列一般是基于堆（heap）結(jié)構(gòu)實(shí)現(xiàn)的，通常是通過數(shù)組或者二叉樹表示。我們知道，vector本質(zhì)上是一個(gè)可變數(shù)組，因此我們可以考慮在 vector 的基礎(chǔ)上實(shí)現(xiàn)優(yōu)先隊(duì)列。

像這樣，在某種組件的基礎(chǔ)上，實(shí)現(xiàn)或者衍生出另一種組件的過程，就叫適配（配接，Adaption），所得到的新組件，就是所謂的適配器（配接器，Adaptor）。適配器相比較于原組件，是一種特定方向的發(fā)展，著重加強(qiáng)了某方面的能力。適配器的優(yōu)點(diǎn)在于它以原組件為底層數(shù)據(jù)結(jié)構(gòu)，貫徹了代碼復(fù)用的原則，大大減少了重復(fù)的工作量，缺點(diǎn)在于它依賴于原組件，如果提供的原組件性能不佳，則適配器的性能必然不佳。

新建頭文件 queue.h，暫時(shí)只考慮C++內(nèi)建類型數(shù)據(jù) ，按照以下原型實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列：

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的時(shí)候，通常我們建立堆的過程是：

在數(shù)組中，下標(biāo) i 從1起算時(shí)， i 的孩子結(jié)點(diǎn)是 i * 2和 i * 2 + 1 。

類似的，如果 i 從0起算，那么根據(jù)數(shù)學(xué)推理有，( i + 1 ) 的孩子結(jié)點(diǎn)是 ( i + 1 ) * 2 和 ( i + 1 ) * 2 + 1。

所以 i 的孩子結(jié)點(diǎn)是， i * 2 + 1 和 i * 2 + 2。

最好采用 i 從 0 起算的做法，因?yàn)槲覀兪褂玫氖莢ector，返回top的時(shí)候可以返回的是vector.front()。

而且最重要的是我們不知道輸入的數(shù)據(jù)是什么，沒辦法在 i = 0 處放置哨兵結(jié)點(diǎn)。

當(dāng)然，如果要實(shí)現(xiàn)下標(biāo) i 從1起算也是可以的，本教程對此不討論，請自行實(shí)現(xiàn)。

我的實(shí)現(xiàn)如下：

在 main.cpp 中簡單測試一下：

輸出正確結(jié)果，我們可以換一種內(nèi)置類型比如double來試試。

一切正常。

歡迎訪問本項(xiàng)目的GitHub倉庫，如果對您有幫助，麻煩給項(xiàng)目一個(gè)star，謝謝！

HuangCheng72/HCSTL: 我的STL實(shí)現(xiàn) (github.com): https://github.com/HuangCheng72/HCSTL