# Benjamin

## STL算法(Algorithms):堆(heap)

1、make_heap：使序列变成堆

template <class RandomAccessIterator>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );

1// range heap example
2#include <iostream>
3#include <algorithm>
4#include <vector>
5using namespace std;
6
7int main () {
8  int myints[] = {10,20,30,5,15};
9  vector<int> v(myints,myints+5);
10
11  make_heap (v.begin(),v.end());
12  cout << "initial max heap   : " << v.front() << endl;
13
14  pop_heap (v.begin(),v.end()); v.pop_back();
15  cout << "max heap after pop : " << v.front() << endl;
16
17  v.push_back(99); push_heap (v.begin(),v.end());
18  cout << "max heap after push: " << v.front() << endl;
19
20  sort_heap (v.begin(),v.end());
21
22  cout << "final sorted range :";
23  for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];
24
25  cout << endl;
26
27  return 0;
28}

29

2、push_heap：压栈(入栈)

template <class RandomAccessIterator>
void push_heap ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
void push_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
3、pop_heap弹栈(出栈)

template <class RandomAccessIterator>
void pop_heap ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
void pop_heap ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );

```  1// range heap example 2#include <iostream> 3#include <algorithm> 4#include <vector> 5using namespace std; 6 7int main () { 8  int myints[] = {10,20,30,5,15}; 9  vector<int> v(myints,myints+5);10  vector<int>::iterator it;1112  make_heap (v.begin(),v.end());13  cout << "initial max heap   : " << v.front() << endl;1415  pop_heap (v.begin(),v.end()); v.pop_back();16  cout << "max heap after pop : " << v.front() << endl;1718  v.push_back(99); push_heap (v.begin(),v.end());19  cout << "max heap after push: " << v.front() << endl;2021  sort_heap (v.begin(),v.end());2223  cout << "final sorted range :";24  for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];2526  cout << endl;2728  return 0;29}304、sort_heap：对堆排序原型：template <class RandomAccessIterator>  void sort_heap ( RandomAccessIterator first, RandomAccessIterator last );template <class RandomAccessIterator, class Compare>  void sort_heap ( RandomAccessIterator first, RandomAccessIterator last,                   Compare comp );范例：  1// range heap example 2#include <iostream> 3#include <algorithm> 4#include <vector> 5using namespace std; 6 7int main () { 8  int myints[] = {10,20,30,5,15}; 9  vector<int> v(myints,myints+5);10  vector<int>::iterator it;1112  make_heap (v.begin(),v.end());13  cout << "initial max heap   : " << v.front() << endl;1415  pop_heap (v.begin(),v.end()); v.pop_back();16  cout << "max heap after pop : " << v.front() << endl;1718  v.push_back(99); push_heap (v.begin(),v.end());19  cout << "max heap after push: " << v.front() << endl;2021  sort_heap (v.begin(),v.end());2223  cout << "final sorted range :";24  for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];2526  cout << endl;2728  return 0;29}30注：例子来源于www.cplusplus.com网站```

posted on 2012-01-12 13:53 Benjamin 阅读(761) 评论(0)  编辑 收藏 引用 所属分类: 泛型编程