导航网站链接怎么做,网站建设课程ppt模板,北京网站改版多少钱,重庆网捷网站建设技术有限公司堆排序
完整可编译运行代码见#xff1a;Github::Data-Structures-Algorithms-and-Applications/_27HeapSort
定义
借助堆进行排序。先用n个待排序的元素初始化一个小根堆#xff0c;然后从堆中逐个提取(即删除元素)元素。初始化的时间复杂度为O(n)#xff0c;大根堆中每…堆排序
完整可编译运行代码见Github::Data-Structures-Algorithms-and-Applications/_27HeapSort
定义
借助堆进行排序。先用n个待排序的元素初始化一个小根堆然后从堆中逐个提取(即删除元素)元素。初始化的时间复杂度为O(n)大根堆中每删除一个元素的时间复杂度为O(logn)。因此总的时间复杂度为O(nlogn)。
实现
main.cpp
#include iostream
#include queue
#include vectorint main() {std::vectorint data {1, 5, 6, 99, 88, 66};std::vectorint res(data.size());// 使用数组初始化小根堆std::priority_queueint, std::vectorint, 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
