c++使用vector建立最大堆和最小堆

一绷落、建堆

vector<int> nums = {9, 6, 2, 4, 7, 0, 1, 8, 3, 5};

1场斑、如果使用nums構建最大堆:

make_heap(nums.begin(), nums.end());
//或
make_heap(nums.begin(), nums.end(), less<int>());

輸出nums的結果為

9 8 2 6 7 0 1 4 3 5 

2蹋岩、如果使用nums構建最小堆:

make_heap(nums.begin(), nums.end(), greater<int>());

輸出nums的結果為

0 3 1 4 5 2 9 8 6 7 

</br>

二增蹭、調整堆

當使用上述的make_heap()建完堆后晕换,如果vector使用push_back()插入數(shù)據(jù)或pop_back()刪除數(shù)據(jù)后午乓,會破壞最大堆/最小堆的性質,所以需要調整堆届巩,常用push_heap()和pop_heap()兩個方法

1硅瞧、push_heap()用法是,vector先push_back()恕汇,后push_heap():

nums.push_back(10);
push_heap(nums.begin(), nums.end(), less<int>());

輸出nums的結果:

//原vector 
9 8 2 6 7 0 1 4 3 5 
//push_back()后
9 8 2 6 7 0 1 4 3 5 10
//push_heap()后
10 9 2 6 8 0 1 4 3 5 7 

2腕唧、pop_heap()用法是,先pop_heap()瘾英,vector后pop_back():

pop_heap(nums.begin(), nums.end(), less<int>());
nums.pop_back();

輸出nums的結果:

//原vector
9 8 2 6 7 0 1 4 3 5 
//pop_heap()后
8 7 2 6 5 0 1 4 3 9 
//pop_back()后
8 7 2 6 5 0 1 4 3 
為什么pop_heap()的用法要反過來呢枣接?

要從我們的目的來考慮,使用pop_heap()的絕大部分目的是要把堆頂元素pop出堆中缺谴,因為它最大或最小但惶。如果先用vector的pop_back(),它刪除的不是堆頂元素(nums[0]),而是vector的最后一個元素膀曾∠嘏溃可見這不是我們想要的結果:對于最大堆,最后一個元素既不是最大添谊,也不一定是最胁圃;對于最小堆斩狱,最后一個元素既不是最小耳高,也不一定是最大。pop出來沒有意義所踊。

觀察pop_heap()對堆做了什么泌枪?

pop_heap()把堆頂元素放到了最后一位,然后對它前面的數(shù)字重建了堆秕岛。這樣一來只要再使用pop_back()把最后一位元素刪除碌燕,就得到了新的堆。

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末瓣蛀,一起剝皮案震驚了整個濱河市陆蟆,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌惋增,老刑警劉巖叠殷,帶你破解...
    沈念sama閱讀 218,122評論 6 505
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異诈皿,居然都是意外死亡林束,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,070評論 3 395
  • 文/潘曉璐 我一進店門稽亏,熙熙樓的掌柜王于貴愁眉苦臉地迎上來壶冒,“玉大人,你說我怎么就攤上這事截歉∨痔冢” “怎么了?”我有些...
    開封第一講書人閱讀 164,491評論 0 354
  • 文/不壞的土叔 我叫張陵瘪松,是天一觀的道長咸作。 經(jīng)常有香客問我,道長宵睦,這世上最難降的妖魔是什么记罚? 我笑而不...
    開封第一講書人閱讀 58,636評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮壳嚎,結果婚禮上桐智,老公的妹妹穿的比我還像新娘末早。我一直安慰自己,他們只是感情好说庭,可當我...
    茶點故事閱讀 67,676評論 6 392
  • 文/花漫 我一把揭開白布然磷。 她就那樣靜靜地躺著,像睡著了一般刊驴。 火紅的嫁衣襯著肌膚如雪样屠。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,541評論 1 305
  • 那天缺脉,我揣著相機與錄音,去河邊找鬼悦穿。 笑死攻礼,一個胖子當著我的面吹牛,可吹牛的內容都是我干的栗柒。 我是一名探鬼主播礁扮,決...
    沈念sama閱讀 40,292評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼瞬沦!你這毒婦竟也來了太伊?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 39,211評論 0 276
  • 序言:老撾萬榮一對情侶失蹤逛钻,失蹤者是張志新(化名)和其女友劉穎僚焦,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體曙痘,經(jīng)...
    沈念sama閱讀 45,655評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡芳悲,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,846評論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了边坤。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片名扛。...
    茶點故事閱讀 39,965評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖茧痒,靈堂內的尸體忽然破棺而出肮韧,到底是詐尸還是另有隱情,我是刑警寧澤旺订,帶...
    沈念sama閱讀 35,684評論 5 347
  • 正文 年R本政府宣布弄企,位于F島的核電站,受9級特大地震影響耸峭,放射性物質發(fā)生泄漏桩蓉。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,295評論 3 329
  • 文/蒙蒙 一劳闹、第九天 我趴在偏房一處隱蔽的房頂上張望院究。 院中可真熱鬧洽瞬,春花似錦、人聲如沸业汰。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,894評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽样漆。三九已至为障,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間放祟,已是汗流浹背鳍怨。 一陣腳步聲響...
    開封第一講書人閱讀 33,012評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留跪妥,地道東北人鞋喇。 一個月前我還...
    沈念sama閱讀 48,126評論 3 370
  • 正文 我出身青樓,卻偏偏與公主長得像眉撵,于是被迫代替她去往敵國和親侦香。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,914評論 2 355

推薦閱讀更多精彩內容