将数组初始化为一棵 max heap, 时间复杂度为 (O(n)).
max heap 的 root 必然是所有 node 中最大的.
排序就是利用这个性质, 将 max heap 的 root 不断 pop 出来, 存入结果数组.
每次 pop 完又会构成一个新的 max heap, 一共 pop (n) 次.
因此最坏情况下 pop 总步数为:
[\sum_{i=1}^{n}{\log{i}} = \log(n!) \leq n\log{n} ]
因此时间复杂度为:
[O(n) + O(n\log{n}) = O(n\log{n}) ]
#include
#include
#include
int main()
{
std::vector vec{ 10,4,6,26,3,54,7,8,23,2 };
std::make_heap(vec.begin(), vec.end(), std::greater());
std::sort_heap(vec.begin(), vec.end());
for (auto i : vec) { printf("%d ", i); }
std::cin.get();
}
Reference | Data Structures, Algoritms, and Applications in C++, Sartaj Sahni
Original: https://www.cnblogs.com/jamesnulliu/p/algoritm_sort_heapsort.html
Author: JamesNULLiu
Title: STL堆排序&时间复杂度分析
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604681/
转载文章受原作者版权保护。转载请注明原作者出处！