ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0

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

Posted on 2010-09-01 17:18 MiYu 阅读(4135) 评论(3)  编辑 收藏 引用 所属分类: ACM_资料

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


Feedback

# re: 学习笔记 -- 关于 STL 中的 heap ( 堆 )  回复  更多评论   

2010-09-08 16:28 by Tanky Woo
小白啊。你最近不行了。。。

堕落了啊。。。

最近怎么不A题了。。。

害哥把你越甩越远了。。。

# re: 学习笔记 -- 关于 STL 中的 heap ( 堆 )  回复  更多评论   

2010-09-10 22:31 by MiYu
题目都好难 做不出来 , 我在看数据结构方面的 T.T

# re: 学习笔记 -- 关于 STL 中的 heap ( 堆 )  回复  更多评论   

2011-05-12 14:37 by 呢喃的歌声
这篇异常给力
转走了。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理