Jan 12

C++ STL Trick 之 **heap 不指定

felix021 @ 2011-1-12 17:20 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(4433) | Via 本站原创 | |
今天跟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)的。。




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]