一绷落、建堆
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()把最后一位元素刪除碌燕,就得到了新的堆。