STL中的heap操作

爱被打了一巴掌 2022-03-21 08:48 205阅读 0赞

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

make\_heap(),

pop\_heap(),

push\_heap(),

sort\_heap(),

is\_heap();

is\_heap() :

注：visual studio的STL实现中没有该函数。

原型如下 :

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

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 规则排序堆.

\#include <iostream>  
\#include <algorithm>  
\#include <vector>  
\#include <functional>  
using namespace std;  
int main()  
\{  
   const int vectorsize=8;  
   typedef vector<int> IntVector;  
   typedef IntVector::iterator IntVectorIt;  
   IntVector Numbers(vectorsize);  
   IntVectorIt it;  
   Numbers\[0\]=4;  
   Numbers\[1\]=10;  
   Numbers\[2\]=70;  
   Numbers\[3\]=10;  
   Numbers\[4\]=30;  
   Numbers\[5\]=69;  
   Numbers\[6\]=96;  
   Numbers\[7\]=100;  
   for(it = Numbers.begin(); it != Numbers.end(); it++)          
    cout << \*it<<" ";   //4 10 70 10 30 69 96 100  
   cout<<endl;  
   make\_heap(Numbers.begin(), Numbers.end()) ;     
   cout << "After calling make\_heap\\n" << endl ;      
     for(it = Numbers.begin(); it != Numbers.end(); it++)     
   cout << \*it << " " ;  // 100 30 96 10 4 69 70 10  
  cout<< endl ;  
 // sort\_heap(Numbers.begin(), Numbers.end()) ;    
 // cout << "After calling sort\_heap\\n" << endl ;     
 // for(it = Numbers.begin(); it != Numbers.end(); it++)        
 //  cout << \*it << " " ;      
 // cout << endl ;  
  make\_heap(Numbers.begin(), Numbers.end()) ;  //一定要调用，因为排序后堆的结构已经被破坏  
  Numbers.push\_back(7) ;  
     push\_heap(Numbers.begin(), Numbers.end()) ;  
      make\_heap(Numbers.begin(), Numbers.end()) ;   
  cout << "After calling push\_heap and make\_heap\\n" << endl ;   
  for(it = Numbers.begin(); it != Numbers.end(); it++)        
   cout << \*it << " " ;     cout << endl ;    //100 30 96 10 4 69 70 10 7  
  pop\_heap(Numbers.begin(), Numbers.end()) ;    
  cout << "After calling pop\_heap\\n" << endl ;      
  for(it = Numbers.begin(); it != Numbers.end(); it++)       
   cout << \*it << " " ;     cout << endl ; //96 30 70 10 4 69 7 10 100

把这几句加上

sort\_heap(Numbers.begin(), Numbers.end()) ;    
  cout << "After calling sort\_heap\\n" << endl ;     
  for(it = Numbers.begin(); it != Numbers.end(); it++)        
   cout << \*it << " " ;

//4 10 70 10 30 69 96 100

// 100 30 96 10 4 69 70 10  
//4 10 10 30 69 70 96 100

//100 69 96 30 4 70 10 10 7

//96 69 70 30 4 7 10 10 100  
若利用STL中的堆函数来实现堆排序，则代码十分简洁。以下是代码

for(it = Numbers.end(); it!=Numbers.begin(); it--)  
   pop\_heap(Numbers.begin(), it);  
           cout << "after 堆排序：\\n";  
        for(it = Numbers.begin(); it != Numbers.end(); it++)  
   cout << \*it << " " ;

// 100 30 96 10 4 69 70 10  
//4 10 10 30 69 70 96 100