堆排序

大根堆

大根堆的定义为一个完全二叉树,且任意一个节点的值都大于它的任意一个左右孩子的值.

大根堆代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;/// @brief 向下调整void adjustdown(vector
           
            &ans, int i, int len){ while (true) { int maxIndex = 2*i+1;//令左右孩子中最大的下标为maxIndex if (maxIndex>len) break; if(maxIndex+1<=len&&ans[maxIndex]

&ans,int i){ while (true) { int parent =i%2?(i-1)/2:(i-2)/2;//父节点 if (parent<0||ans[parent]>=ans[i]) break; swap(ans[parent], ans[i]); i = parent; if(i==0) break; }}/// @brief 建堆void makeheap(vector

&ans, int len){ int i; i = len%2?(len-1)/2:(len-2)/2;//从第一个有孩子的节点开始调整. for (; i>=0&&(2*i+1)<=len; --i) { adjustdown(ans, i,len); }}void print(vector

ans){ for (int i=0; i

ans(a,a+(sizeof(a)/sizeof(int))); int len = (int)ans.size()-1; makeheap(ans,len); while (len) { swap(ans[len], ans[0]); adjustdown(ans, 0,--len); } print(ans); makeheap(ans,(int)ans.size()-1); print(ans); ans.push_back(8); adjustup(ans,(int)ans.size()-1); print(ans); return 0;}

执行结果

-2 0 1 2 3 5 7 9 19 28 28 19 7 9 3 5 1 -2 2 0 28 19 7 9 8 5 1 -2 2 0 3

转载地址：http://dehji.baihongyu.com/