你可能不知道的鼠标键盘
关闭outlook的垃圾邮件过滤功能
Jan
12
C++ STL Trick 之 **heap 
今天跟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就会从大到小排序。可参见源码：
-----
以下是sandy整理的
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
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);
}
_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)的。。
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 。
