Php文档 Php问答行业资讯 Php论坛 Php手册 Php博客

游戏榜单

软件榜单

关闭导航

热搜榜

热门下载

热门标签

关闭搜索

php爱好者> php文档>学习笔记 -- 关于 STL 中的 heap ( 堆 )

学习笔记 -- 关于 STL 中的 heap ( 堆 )

时间：2010-09-01 来源：MiYu

MiYu原创, 转帖请注明 : 转载自 ______________白白の屋

C ++ STL 中与heap 有关的操作有如下几个 :

make_heap(), pop_heap(), push_heap(), sort_heap(), is_heap;

is_heap() :

原型如下 :

1. bool is_heap(iterator start, iterator end);

->判断迭代器[start, end] 区间类的元素是否构成一个堆. 是返回true ,否则返回 false.

2. bool is_heap(iterator start, iterator end, StrictWeakOrdering cmp);

->判断迭代器[start, end] 区间类的元素在cmp条件下是否构成一个堆. 是返回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] 区间内的元素生成一个堆. 默认使用元素类型的 < 操作符进行判断堆的类型, 因此生成的是大顶堆 .

->当使用了版本2时, 系统使用用户定义的 cmp 函数来构建一个堆

->值得注意的是, 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)的数据再做成一个堆。

此时, 原来的首元素位于迭代器 end-1 的位置, 它已不再属于堆的一员!

->如果使用了版本2 , 在交换了首元素和末元素后 ,使用 cmp 规则重新构建一个堆.

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 );

-> 算法假设迭代器区间[start, end-1)内的元素已经是一个有效堆, 然后把 end-1 迭代器所指元素加入堆.

-> 如果使用了 cmp 参数, 将使用 cmp 规则构建堆.

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);

-> 堆结构被完全破坏, 相当于对元素进行排序, 效果和排序算法类似.

-> 如果使用了 cmp 参数, 将使用 cmp 规则排序堆.

代码示例 :

代码

/*
MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
          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