域名申请网页制作网站建设安徽金鹏建设集团网站

堆排序

完整可编译运行代码见：Github::Data-Structures-Algorithms-and-Applications/_27HeapSort

定义

借助堆进行排序。先用n个待排序的元素初始化一个小根堆，然后从堆中逐个提取(即删除元素)元素。初始化的时间复杂度为O(n)，大根堆中每删除一个元素的时间复杂度为O(logn)。因此总的时间复杂度为O(nlogn)。

实现

main.cpp

#include <iostream>
#include <queue>
#include <vector>int main() {std::vector<int> data = {1, 5, 6, 99, 88, 66};std::vector<int> res(data.size());// 使用数组初始化小根堆std::priority_queue<int, std::vector<int>, std::greater<>> pq(data.begin(), data.end());for(int i = 0; i < data.size(); i++){res[i] = pq.top();pq.pop();}for(int re : res)std::cout << re << " ";std::cout << std::endl;return 0;
}

运行结果

"C:\Users\15495\Documents\Jasmine\prj\_Algorithm\Data Structures, Algorithms and Applications in C++\_27HeapSort\cmake-build-debug\_27HeapSort.exe"
1 5 6 66 88 99Process finished with exit code 0