学步园

#include<iostream>
#include<vector>
using namespace std;
/*
*堆排序算法适用于海量元素，时间复杂度为O(nlog(n))，辅助空间也只需O(1);
*有大根堆和小根堆两种，大根堆根节点比两子节点大；小根堆相反。
*此例说明的是小根堆
*/
template <typename T>
void swap(const T &a ,const T &b){
 T t;
 t=a;
 a=b;
 b=t;
}
template <typename T>
void heapsort(vector<T> &arr,int n){
 int i,j,temp;
 T t;
 for(i=n/2;i>0;i--){//调整非叶节点
  t=arr[i];
  temp=i;
  for(j=2*temp;j<=n;j*=2){//满足二倍关系必须保证从1开始
   //if(arr[j]>arr[j+1])j++;//主要莫越界
   //！！遇到边界问题：最后一个节点没有兄弟的情况
   //改进如下
   if(j<n&&arr[j]>arr[j+1])j++;
   if(arr[temp]<=arr[j])break;
   arr[temp]=arr[j];
   temp=j;
  }
  arr[temp]=t;
 }
}
int main(int argc,char* rgv[]){
 int n,i,temp;
 cin>>n;
 vector<int> arr;
 arr.push_back(n);
 for(i=0;i<n;i++){
  cin>>temp;
  arr.push_back(temp);
 }
 heapsort<int>(arr,n);
 //此处要注意一个地方，heapsort<int>(arr,i-1);必须有i-1这个操作，每次arr[i]为剩余元素中最小的元素
 //如果固定为heapsort<int>(arr,n);无法得到正确的结果
 for(i=n;i>1;i--){
  swap(arr[1],arr[i]);
  heapsort<int>(arr,i-1);
 }
 for(i=1;i<=n;i++){
  cout<<arr[i]<<" ";
 }
 return 0;
}

//输出为倒序