C++数据结构--堆排序

Love The Way You Lie 2021-11-10 14:20 271阅读 0赞

**popHeap() ,adjustHeap()详见** [C++数据结构--用向量数组实现大（小）根堆的插入和删除][C_--]

**1.对已经堆化的数组进行堆排序  
![20130808095857656][]  
  
  
  
  
2.向量堆化  
堆化前的向量数组v\{9,12,17,30,50,20,60,65,4,19\}  
![20130808100147140][]  
  
  
堆化过程示意图  
![20130808100211015][]  
  
![20130808100231156][]  
  
  
![20130808100249312][]  
  
  
  
  
实现代码：  
\#include <iostream>  
\#include<vector>  
\#include<functional>  
using namespace std;  
  
  
/\*\*\*\*\*\*\*\*以下省略\*\*\*\*/  
popHeap()  
adjustHeap()  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
  
  
  
  
template<typename T,typename compare>  
//构建堆   
void makeHeap(vector<T> &v,compare cp=compare())  
\{  
  
  
int lastPos=v.size();  
int prtPos=(lastPos-2)/2; //最后一个节点索引为lastPos-1,所以其父结点所以(lastPos-2)/2  
while(prtPos>=0) //循环直到根结点索引   
\{   
adjustHeap(v,prtPos,lastPos,cp); //调整堆v\[prtPos,lastPos-1\]   
prtPos--;   
\}  
\}  
  
  
template<typename T,typename compare>  
/\*堆排序 ：  
\*v为任意向量数组堆  
\*/  
void heapSort(vector<T> &v,compare cp=compare())  
\{  
makeHeap(v,cp);  //构建堆   
for(int i=v.size();i>1;i--) //从后往前进行堆排序  
 popHeap(v,i,cp);  
\}   
  
  
  
  
int main(int argc, char\*\* argv)  
\{  
  
vector<int> vec\{9,12,17,30,50,20,60,65,4,19\};  
heapSort(vec,less\_equal<int>());  
for(int x:vec)  
\{  
cout<<x<<ends;  
\}  
  
return 0;  
\}  
  
  
output:  
 65 60 50 30 20 19 17 12 9 4**

[C_--]: http://blog.csdn.net/piniheaven/article/details/9812531
[20130808095857656]: /images/20211109/dd7e566ad18e4ebaaa9194098e022cbf.png
[20130808100147140]: /images/20211109/23f9e8a6c9a84e03b799e220dc0dea78.png
[20130808100211015]: /images/20211109/418e5980503042c783d4b58dd4bd13f3.png
[20130808100231156]: /images/20211109/b97805dd8e23496496158db0bfdb3611.png
[20130808100249312]: /images/20211109/521a01e1c8d84a8eb9a14794ff154c84.png