短時間了解堆排序

本篇文章是我通過自身實踐總結出來的一種簡單學習堆排序或者是其他排序算法的方法。如有不足，請大家指正，畢竟是學習，主要是了解，主要是網絡中大神們的話太過專業、不怎麼好懂，字也多、我這篇應該算好懂(如不好懂，請指出，我會修改)。

内容包括：

1.堆的分類。

2.如何構造堆(大根堆，以及代碼實作，小根堆同理)。

3.真正堆排序。

一、堆的分類

咱可以把堆（Heap）看成完全二叉樹(葉節點出現在最下層和次下層，最下面一層都連續集中在最左邊的若幹二叉樹)。

形如這樣（下面分析也會結合此圖）：

好的，就這樣别的廢話不說。（注意，上圖已經是一個小根堆了，非終端節點值不大于其左子樹和右子樹，接下來的構造堆則是将它變為大根堆的過程）

二、如何構造堆（将上圖小根堆變為大根堆）

先分析

如何将小根堆變為大根堆呢？其實就是将元素中最大的值放放到堆頂(即将0索引位置的黑色1變為9索引位置的黑色10)，那如何做呢？我們開始。

首先：咱們先進行建堆得第一步，先分析調整一個節點，最後使整個堆構成一個大根堆

既然我們要用到程式中，自然不能單純的想，不過也不能沒有抽象概念。

在程式中我們怎麼把現在的完全二叉樹表示出來呢，數組是一個不錯的表示方法，好那我們就先定義一下這個數組。

上圖中我們的灰色數字就是數組的索引，是以我們的數組可以定義為：

然後我們通過語言來模拟節點的移動，先調整一個節點，咱們看看效果怎麼樣，開始咯!

在這之前我們在想一下，那從第幾個節點開始調整呢？想一下，如果從黑色10節點（灰色數字9索引除）調整，它沒有子節點，顯然如果把它當做一個堆得話，它既是最大的元素也是最小的元素，調整它顯然沒有意義；在想一下如果調整黑色5節點，咱們也把它當做一個堆，它有一個子節點，就是黑色10，顯然子節點比這個黑5要大，是以這個需要調整，就是互換他們；綜上所述，我們要想建構大根堆，我們顯然沒必要從沒有子節點的節點開始調整。這樣我們就可以得到最後一個非葉子節點就是黑色5，也就是節點數/2，由于程式中我們是用索引來訪文數組的，是以還需要減去1，就是節點數/2-1，這樣通過循環就能調整到整個完全二叉樹非葉子節點，黑色1、2、3、4、5。我們先調整一個吧，從最後一個非葉子節點調整就是黑色5。

好的我們開始，我們想像有一個黑盒子，這個盒子很厲害，假設這個堆隻有三個元素，根節點和兩個子節點，但是它不是一個大根堆，但是把這個根節點扔進這個黑盒子之後，就能把它變為最大堆，是不是很神奇。而我們寫的這個構造堆的函數，就是這個黑盒子，好了，開始。

我們先給這個盒子起個名字吧，它的作用是構造堆，我們最好起一個外文的名字，暫時叫HeapStruct(堆構造)……這個盒子肯定得接收點東西，才能有相應的輸出是吧，我們既然是要調整上面那個num[]數組，是以盒子肯定要這個數組，也就是盒子接收的參數一定得有這個數組，好，這樣一個參數确定了；然後這個盒子是不是也得知道從第幾個元素調整呢，是的，畢竟葉子節點沒必要調整，那第二個參數自然是在這個數組中要調整的元素索引了。如果這個盒子再知道這個數組有多少個元素就更好了，那第三個參數就是數組的長度了。好吧，先這樣，如果有需要我們在添加。那我們用c語言模拟這個盒子的話，就成下面這樣了：

/**
* array[] 接收要調整的數組
* i 要調整的元素索引
* nlength 數組的長度
**/
void HeapStruct(int array[],int i,int nlength){
    // 具體構造大根堆的過程
}
           

現在把這個堆（數組num[]）扔進盒子（HeapStruct）中，上面提到我們要從length/2-1索引的節點構造，是以也将length/2-1(4)傳給盒子，最後把數組長度傳入。

這時候調用函數成為：

HeapStruct(num,length/-,length);
           

好了裝進盒子了，盒子要進行怎樣的運作呢？

首先假設黑5有兩個子節點（因為畢竟是二叉樹，一個節點也最多有兩個子節點），如何判斷兩個子節點和父節點誰大誰小進行比較呢？那肯定得先擷取到黑5的兩個子節點。

這裡有一個概念，對于二叉樹，左子節點的索引（比如黑10）9是父節點索引（黑5）4的兩倍多一（2*4+1）,右子節點就簡單了，是左子節點加1((2*4+1)+1)，是以知道了一個節點的索引也就很清楚知道左子節點和右子節點了。

知道了這些我們開始調整：

我們将黑5的左節點索引定義成nChild，那麼右子節點的索引自然就是nChild+1了，那麼我們先獲得左子節點元素值，現在黑子就變成。

/**
* 這個是具體執行函數，參數與上面的調用函數一一對應
*/
void HeapStruct(int array[],i,length){
  int nChild; // 定義左子節點的索引值nChild
  nChild =  * i + ; // 那麼左子節點就是2倍的這個元素的索引+1了 
}
           

這個時候已經擷取到左子節點了。

現在說個新問題，怎麼判斷一個元素的兩個子節點誰大誰小呢？那肯定是要擷取這個元素的右子節點，沒錯是的。 這裡有個這樣的邏輯，就是如果是左子節點比右子節點元素值大，那麼直接調換左子節點與父節點即可這樣就構造了一個三個節點的大根堆，但是如果右子節點比左子節點大，如何呢？那麼調換父節點和右子節點即可了；這樣為了運算簡便，右子節點是左子節點索引+1，為了我們選擇子節點最大值，我們的執行函數就變成：

/**
* 這個是具體執行函數，參數與上面的調用函數一一對應
*/
void HeapStruct(int array[],i,length){
  int nChild; // 定義左子節點的索引值nChild
  nChild =  * i + ; // 那麼左子節點就是2倍的這個元素的索引+1了 

  /**
  * nChild < length-1先判斷一下目前子節點是不是在整個數組長度中，不在的話沒必要看了
  * array[nChild + 1] > array[nChild ]繼續判斷對應在數組中的元素是否右子節點大于左子節點，如果大于，則将子節點值nChild = nChild + 1
  */
  if(nChild < length- && array[nChild + ] > array[nChild ]){
    ++nChild;
  }
}
           

下面開始替換子節點中元素值大的到父節點,既然要替換，首先得有個東西暫時儲存父節點值，暫時叫他nTemp吧，這樣我們的執行函數變為：

/**
* 這個是具體執行函數，參數與上面的調用函數一一對應
*/
void HeapStruct(int array[],i,length){
  int nChild; // 定義左子節點的索引值nChild
  nChild =  * i + ; // 那麼左子節點就是2倍的這個元素的索引+1了 

  /**
  * nChild < length-1先判斷一下目前子節點是不是在整個數組長度中，不在的話沒必要看了
  * array[nChild + 1] > array[nChild ]繼續判斷對應在數組中的元素是否右子節點大于左子節點，如果大于，則将子節點值nChild = nChild + 1
  */
  if(nChild < length- && array[nChild + ] > array[nChild ]){
    ++nChild;
  }

  int nTemp; // 定義一個暫存變量
  if(array[i] < array[nChild]){ // 如果父節點小于子節點最大的值，則替換
    nTmep = array[i]; // 先儲存父節點值到nTemp
    array[i] = array[nChild]; // 将父節點替換為子節點最大值
    array[nChild] = nTemp; // 子節點則換為儲存在變量中的原父節點值
  }else{
    // 什麼都不做
  }
}
           

好了，咱們走一下上面的流程，看一下黑5和黑10會不會調換

我的分析步驟

、傳入數組，索引，數組長度HeapStruct(num,length/-,length)
、nChild =  *  +  = ;
、第一個判斷：if：nChild < length -  ==>  <  (否，不執行)
、第二個判斷：if：array[] < array[] ==>  <  (是，執行) 
      nTemp = array[] ==> nTemp = ;
      array[] = array[] ==> array[] = ;
      array[] = nTemp ==> array[] = ;
、好的，現在是不是黑和黑就替換成功了，完成了我們的調整一個節點的任務。
           

好的，寫着寫着，忽然感覺有點長，休息一下再回來寫，我喝個水吧，最近身體不好，不喝咖啡了。

未完，待續。。。（我可不想分好幾篇寫）