STL 中與heap 有關(guān)的操作有
如下幾個(gè) :
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)成一個(gè)堆. 是返回true ,否則返回 false.
2. bool is_heap(iterator
start, iterator end, StrictWeakOrdering cmp);
->判斷迭代器[start,
end] 區(qū)間類的元素在cmp條件下是否構(gòu)成一個(gè)堆. 是返回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)的元素生成一個(gè)堆. 默認(rèn)使用
元素類型
的 < 操作符
進(jìn)行判斷堆的類型,
因此生成的是大頂堆 .
->當(dāng)使用了
版本2時(shí), 系統(tǒng)使用
用戶定義的 cmp 函數(shù)來構(gòu)建一個(gè)堆
->值得注意的是, 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ù)再做成一個(gè)堆。
此時(shí), 原來的 首元素 位于迭代器 end-1 的位置, 它已不再屬于堆的一員!
->如果使用了
版本2
, 在交換了 首元素和末元素后 ,使用 cmp 規(guī)則 重新構(gòu)建一個(gè)堆.
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)是一個(gè)有效堆, 然后把 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)于對(duì)元素進(jìn)行排序,
效果和排序算法類似.
-> 如果使用了 cmp 參數(shù), 將使用 cmp 規(guī)則排序堆.
示例代碼:
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional> // for greater<>, less<>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
// v.begin and v.end can by replaced by &number[0], &number[9]
int number[10] = {2,1,10,8,90,30,9,98,6,7};
vector<int> v(number,number+10);
//make_heap (v.begin(),v.end()); // the first one is the largest one, others not sure.
//cout << "Initial Max heap: " <<v.front()<< endl;
//make_heap (v.begin(),v.end(),less<int>()); // the first one is the largest one, others not sure.
//cout << "Initial Max heap : " <<v.front()<< endl;
make_heap (v.begin(),v.end(),greater<int>()); // the first one is the smallest one, others not sure.
cout << "Initial Min heap: " <<v.front()<< endl;
//不是真的把最大（最小）的元素從堆中彈出來。而是重新排序堆。它
// 把first和last交換，然后將[first,last-1)的數(shù)據(jù)再做成一個(gè)堆。
//pop_heap (v.begin(),v.end());
//pop_heap (v.begin(),v.end(),less<int>());
pop_heap (v.begin(),v.end(),greater<int>());
v.pop_back(); // Pop up the last one
//cout << "Max heap after pop : " << v.front() << endl;
cout << "Min heap after pop : " << v.front() << endl;
v.push_back(80); // Put to the last one
//push_heap (v.begin(),v.end()); // Keep the first one is the largest one
//push_heap (v.begin(),v.end(), less<int>()); // Keep the first one is the largest one
push_heap (v.begin(),v.end(),greater<int>()); // Keep the first one is the smallest one
//cout << "max heap after push: " << v.front() << endl;
cout << "Min heap after push: " << v.front() << endl;
//sort_heap (v.begin(),v.end()); // sort by descent
//sort_heap (v.begin(),v.end(), less<int>()); // sort by descent
sort_heap (v.begin(),v.end(),greater<int>()); // sort by ascent
cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
cout << endl;
return 0;
}