标题：C++ STL Trick 之 **heap
出处：Felix021
时间：Wed, 12 Jan 2011 17:20:42 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1980

内容：
今天跟Sandy讨论的时候发现的这两个trick。其中第一个trick以前曾经知道，不过太久没用，忘了；第二个trick一直就没发现。

1. make_heap、push_heap、pop_heap默认与其他STL算法一样使用 operator < 进行比较，但是建立的是大根堆，也就是说，pop_heap取出的是heap中的最大值。

2. 在调用sort_heap(begin, end, comparor) 之前，需要保证 [begin, end) 之间是使用同一个 comparor 建立的heap。默认的排序也是使用 operator < ，效果与调用sort是一致的（即默认从小到大排序）：【不要以为】make_heap默认是大根堆，sort_heap就会从大到小排序。可参见源码：sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
      _Compare __comp)
{
  // concept requirements
  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
    _RandomAccessIterator>)
  __glibcxx_requires_valid_range(__first, __last);
  __glibcxx_requires_heap_pred(__first, __last, __comp);

  while (__last - __first > 1)
    std::pop_heap(__first, __last--, __comp);
}


-----

以下是sandy整理的引用
1、heap算法虽然默认都使用的是operator <，但是建立的却是大根堆
2、sort_heap，是对已经成为heap的序列进行sort。本质上就是不断循环pop_heap而已。
3、sort_heap默认使用的也是operator <，排序出来的结果是从小到大的序列。
4、sort_heap算法使用的判别式，必须和之前建立heap的时候使用的判别式一致，比如都是operator <，或者都是operator > 。否则不能保证排序出来的结果是正确的。
5、简而言之，对大根堆进行sort_heap，必须使用operator <，对于小根堆进行sort_heap，必须使用operator >。
6、如果想让大根堆变成一个从大到小的序列，或者想让小根堆变成一个从小到大的序列，不能简单的改变判别式（原因如上所述），而应该保持原有判别式排序，然后调用std::reverse。
7、如果仅仅是想要用堆排序，这样自己封装一个heap_sort函数会更安全：
void heap_sort(RAIterator begin, RAIterator end , Comp op) {
    make_heap(begin, end, op);
    sort_heap(begin, end, op);
}
这样就可以保证建堆的时候和排序的时候用的都是同样的判别式。
8、n次push_heap的算法貌似是O(nlogn)的。。




Generated by Bo-blog 2.1.0