堆排序是一种常见的排序算法，其时间复杂度为O(logN)，重要思想为建堆取极值，根据需求进行排序，如下图：

值得思考的是，二次建堆的过程中，实际上是没有必要将所有元素都进行下调，只需要将根进行下调：

实现代码如下：

template<classT>//建立仿函数模板满足排序需求structCompMax{booloperator()(constT&a,constT&b){returna>b;}};template<classT>structCompMin{booloperator()(constT&a,constT&b){returna<b;}};template<classT,classCom=CompMax<T>>staticvoidHeapSort(vector<T>&list){size_tsize=list.size();GetHeap<T>(list,size);swap(list[0],list[size-1]);while(--size>1){adjustdown<T>(0,size,list);swap(list[0],list[size-1]);}}template<classT,classCom=CompMax<T>>voidadjustdown(intindex,size_tsize,vector<T>&list){Comcomp;size_tparent=index;size_tchild=parent*2+1;while(child<size){if(child+1<size)child=child=comp(list[child],list[child+1])?child:child+1;if(!comp(list[parent],list[child])){std::swap(list[child],list[parent]);parent=child;child=parent*2+1;}elsebreak;}}template<classT,classCom=CompMax<T>>staticvoidGetHeap(vector<int>&list,size_tsize){size_tparent=(size-2)/2;intbegin=parent;Comcomp;while(begin>=0){size_tchild=parent*2+1;while(child<size){if(child+1<size)child=child=comp(list[child],list[child+1])?child:child+1;if(!comp(list[parent],list[child])){swap(list[child],list[parent]);parent=child;child=parent*2+1;}elsebreak;}parent=--begin;}}

如有不足，希望指正，有疑问也希望提出