C++ STL学习(3)

make_heap(first_it,last_it,comp)将[first_it,last_it)以comp做成堆。默认comp为'<'，大顶堆。
push_heap(first_it,last_it,comp)[first,last-1)已经是堆，将[first,last)调整为堆
pop_heap(first_it,last_it,comp)[first,last)已经是堆，*（last-1）在堆外，将*first与*（last-1）交换，然后将[first,last-1)调整为堆。
sort_heap(first_it,last_it,comp)，[first,last-1)已经是堆,将其中的元素进行排序。

以下内容转自：http://blog.sina.com.cn/s/blog_557db8390100meu8.html
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
);


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


以下为MSDN中的详细备注：
Remarks
A heap is a sequence of elements organized like a binary tree. Each heap element corresponds to a tree node. The first value in the sequence [First..Last) is the root and is the largest value in the heap. Every element in the heap satisfies the following: Every element is less than or equal to its parent. The largest element is stored in the root, and all children hold progressively smaller values. The make_heap function converts the range [First..Last) into a heap. The sort_heap function sorts a sequence that was created using the make_heap function. The push_heap function inserts a new value into the heap. The pop_heap function swaps the first and last elements in the heap specified by [First, Last), and then reduces the length of the sequence by one before restoring the heap property. The nonpredicate versions of the heap functions use operator< for comparisons.


示例代码(摘自MSDN  http://msdn.microsoft.com/en-us/library/6y3edk6s(VS.71).aspx )：

// heapfunc.cpp // compile with: /EHsc // // Functions: //    make_heap : convert a sequence to a heap //    sort_heap : sort a heap //    push_heap : insert an element in a heap //    pop_heap  : remove the top element from a heap // disable warning C4786: symbol greater than 255 characters, // okay to ignore #pragma warning(disable: 4786) #include <iostream> #include <algorithm> #include <functional> #include <vector> using namespace std; int main() {     const int VECTOR_SIZE = 8 ;     // Define a template class vector of int     typedef vector<int > IntVector ;     //Define an iterator for template class vector of strings     typedef IntVector::iterator IntVectorIt ;     IntVector Numbers(VECTOR_SIZE) ;     IntVectorIt it ;     // Initialize vector Numbers     Numbers[0] = 4 ;     Numbers[1] = 10;     Numbers[2] = 70 ;     Numbers[3] = 10 ;     Numbers[4] = 30 ;     Numbers[5] = 69 ;     Numbers[6] = 96 ;     Numbers[7] = 100;     // print content of Numbers     cout << "Numbers { " ;     for(it = Numbers.begin(); it != Numbers.end(); it++)         cout << *it << " " ;     cout << " }\n" << endl ;     // convert Numbers into a heap     make_heap(Numbers.begin(), Numbers.end()) ;     cout << "After calling make_heap\n" << endl ;     // print content of Numbers     cout << "Numbers { " ;     for(it = Numbers.begin(); it != Numbers.end(); it++)         cout << *it << " " ;     cout << " }\n" << endl ;
//注意：该部分排序后将破坏堆的结构！     // sort the heapified sequence Numbers     sort_heap(Numbers.begin(), Numbers.end()) ;     cout << "After calling sort_heap\n" << endl ;     // print content of Numbers     cout << "Numbers { " ;     for(it = Numbers.begin(); it != Numbers.end(); it++)         cout << *it << " " ;     cout << " }\n" << endl ;
　　　　//若此前调用了sort_heap，为了保持堆的性质，在调用push_heap之前必须调用该行，否则程序将崩溃。此处原文未调用，故原文测试程序有invalid heap错误。
   // you need to call make_heap to re-assert the     // heap property     make_heap(Numbers.begin(), Numbers.end()) ;     //insert an element in the heap     Numbers.push_back(7) ;
    push_heap(Numbers.begin(), Numbers.end()) ;
    // you need to call make_heap to re-assert the     // heap property     make_heap(Numbers.begin(), Numbers.end()) ;     cout << "After calling push_heap and make_heap\n" << endl ;     // print content of Numbers     cout << "Numbers { " ;     for(it = Numbers.begin(); it != Numbers.end(); it++)         cout << *it << " " ;     cout << " }\n" << endl ;     // remove the root element from the heap Numbers     pop_heap(Numbers.begin(), Numbers.end()) ;     cout << "After calling pop_heap\n" << endl ;     // print content of Numbers     cout << "Numbers { " ;     for(it = Numbers.begin(); it != Numbers.end(); it++)         cout << *it << " " ;     cout << " }\n" << endl ; }

若利用STL中的堆函数来实现堆排序，则代码十分简洁。以下是代码：
cout << "堆排序example：\n";
cout << "Numbers { " ;
for(it = Numbers.begin(); it != Numbers.end(); it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;
make_heap(Numbers.begin(), Numbers.end());
for(it = Numbers.end(); it!=Numbers.begin(); it--)
  pop_heap(Numbers.begin(), it);
cout << "after 堆排序：\n";
cout << "Numbers { " ;
for(it = Numbers.begin(); it != Numbers.end(); it++)
        cout << *it << " " ;
    cout << " }\n" << endl ;

事实上，sort_heap就是堆排序的一种实现。