sort_heap存在的原因

Question

在浏览标准库的不太知名的部分时,我偶然发现了std :: sort_heap.但我不明白为什么它存在,因为有一个名为std :: sort的自由函数.

另请注意,复杂性是相同的.

所以我的问题是:sort_heap存在的理由是什么.

Answer 1

sort_heap假设输入已经是堆的形式.这意味着它理论上可以更有效地工作std::sort,因为对输入的顺序有一些限制(不同于std::sort必须对所有输入起作用).

正如评论中所提到的,值得注意的是,这些性能优势绝不会得到保证,而且显然取决于输入数据,因此如果性能很重要,则无法进行性能分析.

这不一定是真的 - 由于缓存局部性不好，堆排序的性能可能比快速/合并排序差。 (2认同)
@Konrad我不是,真的.我只是做了一些测试,虽然我没有声称它们是完美的,但std :: sort始终比std :: sort_heap更快(不是更快).另外,请查看本文:http://www.lamarca.org/anthony/pubs/cachesort.pdf,第19-21页仅显示性能图 - 尽管它是整个'先构建堆然后排序',但它是通常比快速排序或合并排序慢两倍.这篇论文可能有点过时,但它是我在这个主题上找到的最好的资料. (2认同)
@Ivan 确实不错的研究。荣誉。 (2认同)

Answer 2

sort_heap 将堆 [1] [first, last) 转换为排序范围。请注意，这不是稳定的 > 排序：不保证保留等效元素的相对顺序。

根据实现， std::sort 在最坏情况下可能会为您提供 O(N^2) 复杂度，并且适用于未排序的数据集。std::sort_heap 在堆上工作并且总是给你 O(nlogn)