MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋 
C ++ STL 中與heap 有關(guān)的操作有 如下幾個 :
make_heap(), pop_heap(), push_heap(), sort_heap(), is_heap;
is_heap() :
原型如下 :
1. bool is_heap(iterator start, iterator end);
->判斷迭代器[start, end] 區(qū)間類的元素是否構(gòu)成一個堆. 是返回true ,否則返回 false.
2. bool is_heap(iterator start, iterator end, StrictWeakOrdering cmp);
->判斷迭代器[start, end] 區(qū)間類的元素在cmp條件下是否構(gòu)成一個堆. 是返回true ,否則返回 false.
make_heap() :
原型如下 :
1. void make_heap( random_access_iterator start, random_access_iterator end );
2. void make_heap( random_access_iterator start, random_access_iterator end, StrictWeakOrdering cmp );
->以 迭代器[start , end] 區(qū)間內(nèi)的元素生成一個堆. 默認(rèn)使用 元素類型 的 < 操作符 進(jìn)行判斷堆的類型, 因此生成的是大頂堆 .
->當(dāng)使用了 版本2時, 系統(tǒng)使用 用戶定義的 cmp 函數(shù)來構(gòu)建一個堆
->值得注意的是, make_heap 改變了 迭代器所指向的 容器 的值.
pop_heap() :
原型如下 :
1. void pop_heap( random_access_iterator start, random_access_iterator end );
2. void pop_heap( random_access_iterator start, random_access_iterator end, StrictWeakOrdering cmp );
->pop_heap() 并不是真的把最大（最小）的元素從堆中彈出來. 而是重新排序堆. 它把首元素和末元素交換，然后將[first,last-1)的數(shù)據(jù)再做成一個堆。
此時, 原來的 首元素 位于迭代器 end-1 的位置, 它已不再屬于堆的一員!
->如果使用了 版本2 , 在交換了 首元素和末元素后 ,使用 cmp 規(guī)則 重新構(gòu)建一個堆.
push_heap() :
原型如下 :
1. void push_heap( random_access_iterator start, random_access_iterator end );
2. void push_heap( random_access_iterator start, random_access_iterator end, StrictWeakOrdering cmp );
-> 算法假設(shè)迭代器區(qū)間[start, end-1)內(nèi)的元素已經(jīng)是一個有效堆, 然后把 end-1 迭代器所指元素加入堆.
-> 如果使用了 cmp 參數(shù), 將使用 cmp 規(guī)則構(gòu)建堆.
sort_heap() :
原型如下 :
1. void sort_heap (random_access_iterator start, random_access_iterator end);
2. void sort_heap (random_access_iterator start, random_access_iterator end, StrictWeakOrdering cmp);
-> 堆結(jié)構(gòu)被完全破壞, 相當(dāng)于對元素進(jìn)行排序, 效果和排序算法類似.
-> 如果使用了 cmp 參數(shù), 將使用 cmp 規(guī)則排序堆.
代碼示例 :
代碼
/*
MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋
http://www.cnblog.com/MiYu
Author By : MiYu
Test : 1
Program : heap_test
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main ()
{
vector <int> vec;
for ( int i = 1; i <= 10; ++i ) vec.push_back(i);
for ( int i = 0; i < 10; ++ i ){
cout << vec[i] << " ";
} cout << endl;
make_heap ( vec.begin(), vec.end() );
cout << "\nAfter Make_Heap: " << endl;
for ( int i = 0; i < 10; ++i ){
cout << vec[i] << " ";
} cout << endl;
vec.push_back ( 11 );
cout << "\nAfter Push_Heap: " << endl;
push_heap ( vec.begin(), vec.end() );
for ( int i = 0; i < 10; ++i ){
cout << vec[i] << " ";
} cout << endl;
cout << "\nAfter Pop_Heap: " << endl;
pop_heap ( vec.begin(), vec.end() );
for ( int i = 0; i < 11; ++i ){
cout << vec[i] << " ";
} cout << endl;
cout << "\nMake_heap Again! " << endl;
make_heap ( vec.begin(), vec.end() );
cout << "\nAfter Sort_Heap: " << endl;
sort_heap ( vec.begin(), vec.end() );
for ( int i = 0; i < 11; ++i ){
cout << vec[i] << " ";
} cout << endl;
system ( "pause" );
return 0;
}
OutPut:
1 2 3 4 5 6 7 8 9 10
After Make_Heap:
10 9 7 8 5 6 3 1 4 2
After Push_Heap:
11 10 7 8 9 6 3 1 4 2
After Pop_Heap:
10 9 7 8 5 6 3 1 4 2 11
Make_heap Again!
After Sort_Heap:
1 2 3 4 5 6 7 8 9 10 11
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
int myints[] = {10,20,30,5,15};
vector<int> v(myints,myints+5);
vector<int>::iterator it;
make_heap (v.begin(),v.end());
cout << "initial max heap : " << v.front() << endl;
pop_heap (v.begin(),v.end()); v.pop_back();
cout << "max heap after pop : " << v.front() << endl;
v.push_back(99); push_heap (v.begin(),v.end());
cout << "max heap after push: " << v.front() << endl;
sort_heap (v.begin(),v.end());
cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
cout << endl;
return 0;
}
OutPut :
initial max heap : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99