本文主要是介绍算法导论CLRS 6 堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*6 堆排序*HEAP-SORT*/
#include<cstdlib>
#include<iostream>
#include<vector>
#include<iomanip>using namespace std;
typedef vector<int>::iterator ivecIte;
#define parent(i) (0==(i%2) ? i/2 : (i-1)/2)
#define left(i) 2*i
#define right(i) 2*i+1size_t chkivIte(ivecIte iteB, ivecIte iteE)
{if(iteB > iteE) {cout<<"wrong in iterator range!"<<endl;exit(0);}return iteE - iteB;
}
void maxHeapify(vector<int> &ivec, ivecIte iteB, ivecIte iteE, ivecIte iteChk)
{size_t heapSize = chkivIte(iteB, iteE);//将迭代器转换成堆的下标size_t i = iteChk - iteB + 1;ivecIte largeIte = iteChk;//必要的初始化/*条件传送指令要小心使用*条件传送会提前运算两种结果后再判断*必须先判断后使用条件传送指令*/if(left(i)<=heapSize) {ivecIte leftIte = iteB+left(i)-1;largeIte = (*leftIte>*iteChk) ? leftIte : iteChk;}if(right(i)<=heapSize) {ivecIte rightIte = iteB+right(i)-1;largeIte =(*rightIte>*largeIte) ? rightIte : largeIte;}if(iteChk != largeIte) {*iteChk = (*iteChk) ^ (*largeIte);*largeIte = (*iteChk) ^ (*largeIte);*iteChk = (*iteChk) ^ (*largeIte);maxHeapify(ivec, iteB, iteE, largeIte);}
}
void buildMaxHeap(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{size_t heapSize = chkivIte(iteB, iteE);size_t indx = heapSize/2;ivecIte iteChk;for(size_t t = indx; 0 != t; --t) {iteChk = iteB + t - 1; maxHeapify(ivec, iteB, iteE, iteChk);}
}
void heapSort(vector<int> &ivec, ivecIte iteB, ivecIte iteE)
{size_t heapSize = chkivIte(iteB, iteE);buildMaxHeap(ivec, iteB, iteE);ivecIte iteT;for(size_t t = heapSize; 1 != t; --t) {iteT =iteB + t - 1;//iteT肯定大于iteB,所以可以用^位操作符交换*iteT = (*iteB) ^ (*iteT);*iteB = (*iteB) ^ (*iteT);*iteT = (*iteB) ^ (*iteT);maxHeapify(ivec, iteB, iteT, iteB);}
}
int main()
{vector<int> ivec;cout<<"input some integers with end-of-file!"<<endl;int inData;while(cin>>inData)ivec.push_back(inData);heapSort(ivec, ivec.begin(), ivec.end());for(ivecIte ite = ivec.begin(); ivec.end() != ite; ++ite)cout<<setw(5)<<*ite;cout<<endl;system("PAUSE");return EXIT_SUCCESS;
}这篇关于算法导论CLRS 6 堆排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
