/*堆排序思想:[完全二叉樹的定義:前 h-1 層為滿二叉樹一最后一層連續缺失右結點(即右子女)]，(大根堆升序排序，小根堆降序排列)   首先堆是一個完全二叉樹 ，根據數組下標就可建成了一棵完全二叉樹   其次:while(有雙親){     A: 調整為一個大根堆         【Adjust()函數實現】     B: 交換最后一個葉子結點和根結點    【Swap()函數實現】     C: 砍掉最后一個葉子結點      【即元素個數 n--】   } */  #include <iostream> #define N 100  using namespace std;   int b[N]={0};    //存儲數據的數組  int n=0;      //記錄數據的總個數【0單元不要,實際元素個數為(n-1)個】  void Swap(int *x,int *y){   int t;   t=*x;   *x=*y;   *y=t; }   void Adjust(){   int p;         //記錄雙親結點    int tag=1;       //記錄是否已經調整為大根堆(標志性的變量)   while(tag){       //判斷是否已經調整好為大根堆     p=(n-1)/2;     //最后一個雙親結點的下標     tag=0;       //凡是交換后，tag=1,標志著還沒有調整為大根堆，否則繼續調整      while(p>0){     //確保有雙親結點       if(b[p]<b[2*p]){     //若根結點大于左子女結點，就交換          Swap(&b[p],&b[2*p]);         tag=1;       }       if(2*p+1<n && b[p]<b[2*p+1]){ //若存在右子女，并且根結點大于右子女結點，就交換          Swap(&b[p],&b[2*p+1]);         tag=1;            }       p--;        //直到最后一個雙親結點調整完      }    }  }  void HeapSort(){   while(n>2){         //保證有雙親結點      Adjust();        //調整大根堆函數     Swap(&b[1],&b[n-1]);  //將最后一個葉子結點和根結點交換      n--;          //裁剪最后的葉子結點    } }       int main(void){   int i,m;   cout<<"請輸入數據的總數【0單元不要,實際元素個數為(n-1)個】:"<<endl;   cin>>n;   m=n;   cout<<"請輸入各個數據【0單元不要,實際元素個數為(n-1)個】:"<<endl;   b[0]=0;   for(i=1;i<n;i++){     cin>>b[i];   }   HeapSort();           //堆排序   cout<<"大根堆升序排列為:"<<endl;   for(i=1;i<m;i++){     cout<<b[i]<<" ";   }    cout<<endl;   return 0; }