快捷導(dǎo)航

深入理解堆排序及其分析

更新時(shí)間：2013年05月24日 15:08:15 作者：

本篇文章是對(duì)堆排進(jìn)行了詳細(xì)的分析以及介紹，需要的朋友參考下

記得在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候一味的想用代碼實(shí)現(xiàn)算法，重視的是寫(xiě)出來(lái)的代碼有一個(gè)正確的輸入，然后有一個(gè)正確的輸出，那么就很滿(mǎn)足了。從網(wǎng)上看了許多的代碼，看了之后貌似懂了，自己寫(xiě)完之后也正確了，但是不久之后就忘了，因?yàn)榇竽X在回憶的時(shí)候，只依稀記得代碼中的部分，那么的模糊，根本不能再次寫(xiě)出正確的代碼，也許在第一次寫(xiě)的時(shí)候是因?yàn)閰⒖剂藙e人的代碼，看過(guò)之后大腦可以進(jìn)行短暫的高清晰記憶，于是欺騙了我，以為自己寫(xiě)出來(lái)的，滿(mǎn)足了成就感?？墒谴a是計(jì)算機(jī)識(shí)別的，而我們更喜歡文字，圖像。所以我們?cè)趯W(xué)習(xí)算法的時(shí)候要注重算法的原理以及算法的分析，用文字，圖像表達(dá)出來(lái)，然后當(dāng)需要用的時(shí)候再將文字轉(zhuǎn)換為代碼。記憶分為三個(gè)步驟：編碼，存儲(chǔ)和檢索，就以學(xué)習(xí)為例，先理解知識(shí)，再歸納知識(shí)，最后鞏固知識(shí)，為了以后的應(yīng)用而方便檢索知識(shí)。

堆排序過(guò)程
堆分為大根堆和小根堆，是完全二叉樹(shù)。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。

既然是堆排序，自然需要先建立一個(gè)堆，而建堆的核心內(nèi)容是調(diào)整堆，使二叉樹(shù)滿(mǎn)足堆的定義（每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值）。調(diào)堆的過(guò)程應(yīng)該從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，假設(shè)有數(shù)組A = {1, 3, 4, 5, 7, 2, 6, 8, 0}。那么調(diào)堆的過(guò)程如下圖，數(shù)組下標(biāo)從0開(kāi)始，A[3] = 5開(kāi)始。分別與左孩子和右孩子比較大小，如果A[3]最大，則不用調(diào)整，否則和孩子中的值最大的一個(gè)交換位置，在圖1中是A[7] > A[3] > A[8]，所以A[3]與A[7]對(duì)換，從圖1.1轉(zhuǎn)到圖1.2。

所以建堆的過(guò)程就是

復(fù)制代碼代碼如下:

for ( i = headLen/2; i >= 0; i++)

do AdjustHeap(A, heapLen, i)

建堆完成之后，堆如圖1.7是個(gè)大根堆。將A[0] = 8 與 A[heapLen-1]交換,然后heapLen減一，如圖2.1，然后AdjustHeap(A, heapLen-1, 0)，如圖2.2。如此交換堆的第一個(gè)元
素和堆的最后一個(gè)元素，然后堆的大小heapLen減一，對(duì)堆的大小為heapLen的堆進(jìn)行調(diào)堆，如此循環(huán)，直到heapLen == 1時(shí)停止，最后得出結(jié)果如圖3。

復(fù)制代碼代碼如下:

/*
     輸入：數(shù)組A，堆的長(zhǎng)度hLen，以及需要調(diào)整的節(jié)點(diǎn)i
     功能：調(diào)堆
 */

 void AdjustHeap(int A[], int hLen, int i)
 {
     int left = LeftChild(i);  //節(jié)點(diǎn)i的左孩子
     int right = RightChild(i); //節(jié)點(diǎn)i的右孩子節(jié)點(diǎn)
     int largest = i;
     int temp;

     while(left < hLen || right < hLen)
     {
         if (left < hLen && A[largest] < A[left])
         {
             largest = left;
         }

         if (right < hLen && A[largest] < A[right])
         {
             largest = right;
         }

         if (i != largest)   //如果最大值不是父節(jié)點(diǎn)
         {
              temp = A[largest]; //交換父節(jié)點(diǎn)和和擁有最大值的子節(jié)點(diǎn)交換
              A[largest] = A[i];
              A[i] = temp;

             i = largest;         //新的父節(jié)點(diǎn)，以備迭代調(diào)堆
             left = LeftChild(i);  //新的子節(jié)點(diǎn)
             right = RightChild(i);
         }
         else
         {
             break;
         }
     }
 }

 /*
     輸入：數(shù)組A，堆的大小hLen
     功能：建堆
 */
 void BuildHeap(int A[], int hLen)
 {
     int i;
     int begin = hLen/2 - 1;  //最后一個(gè)非葉子節(jié)點(diǎn)
     for (i = begin; i >= 0; i--)
     {
         AdjustHeap(A, hLen, i);  
     }
 }

 /*
     輸入：數(shù)組A，待排序數(shù)組的大小aLen
     功能：堆排序
 */
 void HeapSort(int A[], int aLen)
 {
     int hLen = aLen;
     int temp;

     BuildHeap(A, hLen);      //建堆

     while (hLen > 1)
     {
         temp = A[hLen-1];    //交換堆的第一個(gè)元素和堆的最后一個(gè)元素
         A[hLen-1] = A[0];
         A[0] = temp;
         hLen--;        //堆的大小減一
         AdjustHeap(A, hLen, 0);  //調(diào)堆
     }
 }

性能分析
•調(diào)堆：上面已經(jīng)分析了，調(diào)堆的運(yùn)行時(shí)間為O(h)。
•建堆：每一層最多的節(jié)點(diǎn)個(gè)數(shù)為n1 = ceil(n/(2^(h+1))),

因此，建堆的運(yùn)行時(shí)間是O(n)。
•循環(huán)調(diào)堆（代碼67-74），因?yàn)樾枰{(diào)堆的是堆頂元素，所以運(yùn)行時(shí)間是O(h) = O(floor(logn))。所以循環(huán)調(diào)堆的運(yùn)行時(shí)間為O(nlogn)。
總運(yùn)行時(shí)間T(n) = O(nlogn) + O(n) = O(nlogn)。對(duì)于堆排序的最好情況與最壞情況的運(yùn)行時(shí)間，因?yàn)樽顗呐c最好的輸入都只是影響建堆的運(yùn)行時(shí)間O(1)或者O(n)，而在總體時(shí)間中占重要比例的是循環(huán)調(diào)堆的過(guò)程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最壞情況下，堆排序的運(yùn)行時(shí)間都是O(nlogn)。而且堆排序還是原地算法（in-place algorithm）。

您可能感興趣的文章: