C++STL之堆排序算法
发布时间:2020-12-16 07:47:19 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 /**************************优先队列的实现选择: 链表(表头插入为O(N),删除时遍历O(N))或者让表插入时保持排序 二叉树(删除和插入都是O(logN))
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 /************************** 优先队列的实现选择: 链表(表头插入为O(N),删除时遍历O(N))或者让表插入时保持排序 二叉树(删除和插入都是O(logN)) 可以达到NlogN 的时间复杂度的排序,就是使用二叉堆实现 使用的排序算法就是堆排序 使用一个附加数组,存储空间增加一倍 (或者将删除的最小数放入堆的最后) //?? 因为只会复制一次,时间复杂度并不会显著增加 //?? ***************************/ // heapSort.h // // #pragma once #include "stdafx.h" #include <vector> using namespace std; int leftChild(int hole) //查找节点的左子树 { return hole*2 + 1; } // 最小值堆 template <typename T> void percolateMinDown(int hole,vector<T>& vec) // vec为原数组,hole为当前要排序的堆的空穴 { int child; T temp = vec[hole]; for (; leftChild(hole)< vec.size(); hole = child) { child = leftChild(hole); //chlid为hole的左子树,child+1为hole的右子树 if (leftChild(hole) != vec.size() && vec[child+1] < vec[child]) //注意数组访问不要越界 { child ++; //取左子树和右子树中的最小值 } if ( temp > vec[child]) //如果左子树和右子树中的最小值仍然比要空穴的值小,则其将最小值移到当前空穴 { vec[hole] = vec[child]; } else //如果左子树和右子树中的最小值仍然比要空穴的值大,则当前空穴就是其最终位置 break; } vec[hole] = temp; } template <typename T> void heapMinSort(vector<T>& vec) { // vector<T> tempVector(vec.size()+1); // for (int i = 0; i < vec.size(); i++) // { // tempVector[i] = vec[i]; //这里并没有用到附加数组 // } int hole = vec.size()/2; for (; hole >= 0; hole--) // 从大到小依次计算空穴的值 { percolateMinDown(hole,vec); } } // 最大值堆 template <typename T> void percolateMaxDown(int hole,vector<T>& vec) { int child; T temp = vec[hole]; for (;leftChild(hole) < vec.size(); hole = child) { child = leftChild(hole); if ( leftChild(hole) != vec.size() && vec[child] < vec[child+1]) //大根堆中取两个子树的较大者 { child++; } if (temp < vec[child]) //将左子树和右子树中的较大者移入空穴 { vec[hole] = vec[child]; } else break; } vec[hole] = temp; } template <typename T> void heapMaxSort(vector<T>& vec) { int hole = vec.size()/2; for (; hole >= 0; hole--) // 从大到小依次计算空穴的值 { percolateMaxDown(hole,vec); } } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |