[演算法] 堆積排序法(Heap Sort)
YehYeh\'s Notepad yehyeh@gmail.com 

[演算法(Algorithm)] 堆積排序法(Heap Sort)

  • 堆積樹(Heap Tree):又叫累堆
    • 二元樹的一種 每個父節點最多兩個子節點
    • 堆積樹為完全二元樹(Complete Binary Tree)的一種
    • 最小堆積(Min Heap):父節點的值小於子節點
      • 樹根(root)一定最所有節點的最小值
    • 最大堆積(Max Heap):父節點的值大於子節點
      • 樹根(root)一定最所有節點的最大值
    • 兄弟節點的大小不重要
  • 堆積排序法為選擇排序法的改良
  • 堆積排序作法
    • 將數列轉換成Max Heap
    • 排序 (最大堆積樹(Max Heap)樹根一定是最大值)
      • 樹根(最大值)最後一個節點調換,將最後一個節點(原樹根)取出,並加入已排序數列
        • 相當於對Max Heap Tree作Delete MaxNode
      • 對整棵樹重新調整為最大堆積樹 調整後樹根為Max Node
      • 重複步驟1、2
    • 將數列轉換成Min Heap
    • 排序 (最小堆積樹(Min Heap)樹根一定是最小值)
      • 樹根(最小值)最後一個節點調換,將最後一個節點(原樹根)取出,並加入已排序數列
        • 相當於對Min Heap Tree作Delete MinNode
      • 對整棵樹重新調整為最小堆積樹 調整後樹根為Min Node
      • 重複步驟1、2
    • 將數列裡的數值依序加入Heap Tree 新加入的值為最後一個樹葉節點
    • 每加入一個數值,則整棵樹重新調整為Heap Tree
      • 要由小排到大 Min Heap
      • 要由大排到小 Max Heap
  • 取出:實作時一般是縮減Heap Tree的範圍
      • 取出前Heap Tree陣列範圍為A[0-9]
      • 取出最後一個樹枼節點後,Heap Tree陣列範圍為A[0-8]
  • 陣對映到二元樹
    陣對映到二元樹
  • 二元樹調整為Max Heap
    • 二元樹有floor(n/2)個內部節點
    • 由後往前以每個內部節點為Root,作堆積化(Heapify)
    • 堆積化(Heapify)
      • 令Root的左、右子樹皆符合Heap,僅Root不符合Heap
      • 令Root、左子元素、右子元素3個元素中,最大者為MaxNode
      • 若Root = MaxNode 結束
      • 若左子元素或右子元素 = MaxNode
        • 將Root與MaxNode作對調(Swap)
        • 若對調完的Root有子節點 對原來的Root作Heapify
    • 原始數列的二元樹

      原始數列的二元樹
      依序對3個非樹葉節點: 2[57], 1[14], 0[38]進行Heapify

      有3個非樹葉節點:0[38], 1[14], 2[57]
      以2[57]為Root進行Heapify
      Root[57]最大結束
      以2[57]為Root進行Heapify
      以1[14]為Root進行Heapify
      3[59]最大 3[59]與Root[14]做Swap
      3[14]沒有子節點結束
      以1[14]為Root進行Heapify
      以0[38]為Root進行Heapify
      1[59]最大 1[59]與Root[38]做Swap
      1[38]有子節點 對1[38]作Heapify
      以0[38]為Root進行Heapify
      以1[38]為Root進行Heapify
      4[52]最大 4[52]與Root[38]做Swap
      4[38]沒有子節點結束
      以1[38]為Root進行Heapify
      Max Heap


      Max Heap
  • Heap Sort(Max Heap)圖解:
    • 二元樹調整為Max Heap
      原始數列的二元樹
      原始數列的二元樹
      以4[45]為Root作Heapify
      9[57]最大 9[57]與4[45]做Swap
      9[45]沒有子節點 結束
      以4[45]為Root作Heapify
      以3[79]為Root作Heapify
      Root[79]最大 結束
      以3[79]為Root作Heapify
      以2[92]為Root作Heapify
      Root[92]最大 結束
      以2[92]為Root作Heapify
      以1[51]為Root作Heapify
      3[79]最大 3[79]與1[51]做Swap
      3[51]有子節點 對3[51]作Heapify
      以1[51]為Root作Heapify
      以3[51]為Root作Heapify
      7[70]最大 7[70]與3[51]做Swap
      7[51]沒有子節點 結束
      以3[51]為Root作Heapify
      以0[14]為Root作Heapify
      2[92]最大 2[92]與0[14]做Swap
      2[14]有子節點 對2[14]作Heapify
      以0[14]為Root作Heapify
      以2[14]為Root作Heapify
      6[75]最大 6[75]與2[14]做Swap
      6[14]沒有子節點 結束
      以2[14]為Root作Heapify
      Max Heap
      Max Heap
    • 排序
      Max Heap
      Max Heap
      將0[92]與9[45]作Swap
      將0[92]與9[45]作Swap
      以0[45]為Root作Heapify
      1[79]最大 1[79]與0[45]做Swap
      1[45]有子節點 對1[45]作Heapify
      以0[45]為Root作Heapify
      以1[45]為Root作Heapify
      3[70]最大 3[70]與1[45]做Swap
      3[45]有子節點 對3[45]作Heapify
      以1[45]為Root作Heapify
      以3[45]為Root作Heapify
      7[51]最大 7[51]與3[45]做Swap
      7[45]沒有子節點 結束
      以3[45]為Root作Heapify
      將0[79]與8[3]作Swap
      將0[79]與8[3]作Swap
      以0[3]為Root作Heapify
      2[75]最大 2[75]與0[3]做Swap
      2[3]有子節點 對2[3]作Heapify
      以0[3]為Root作Heapify
      以2[3]為Root作Heapify
      6[14]最大 6[14]與2[3]做Swap
      6[3]沒有子節點 結束
      以2[3]為Root作Heapify
      將0[75]與7[45]作Swap
      將0[75]與7[45]作Swap
      以0[45]為Root作Heapify
      1[70]最大 1[70]與0[45]做Swap
      1[45]有子節點 對1[45]作Heapify
      以0[45]為Root作Heapify
      以1[45]為Root作Heapify
      4[57]最大 4[57]與1[45]做Swap
      4[45]沒有子節點 結束
      以1[45]為Root作Heapify
      將0[70]與6[3]作Swap
      將0[70]與6[3]作Swap
      以0[3]為Root作Heapify
      1[57]最大 1[57]與0[3]做Swap
      1[3]有子節點 對1[3]作Heapify
      以0[3]為Root作Heapify
      以1[3]為Root作Heapify
      3[51]最大 3[51]與1[3]做Swap
      3[3]沒有子節點 結束
      以1[3]為Root作Heapify
      將0[57]與5[2]作Swap
      將0[57]與5[2]作Swap
      以0[2]為Root作Heapify
      1[51]最大 1[51]與0[2]做Swap
      1[2]有子節點 對1[2]作Heapify
      以0[2]為Root作Heapify
      以1[2]為Root作Heapify
      4[45]最大 4[45]與1[2]做Swap
      4[2]沒有子節點 結束
      以1[2]為Root作Heapify
      將0[51]與4[2]作Swap
      將0[51]與4[2]作Swap
      以0[2]為Root作Heapify
      1[45]最大 1[45]與0[2]做Swap
      1[2]有子節點 對1[2]作Heapify
      以0[2]為Root作Heapify
      以1[2]為Root作Heapify
      3[3]最大 3[3]與1[2]做Swap
      3[2]沒有子節點 結束
      以1[2]為Root作Heapify
      將0[45]與3[2]作Swap
      將0[45]與3[2]作Swap
      以0[2]為Root作Heapify
      2[14]最大 2[14]與0[2]做Swap
      2[2]沒有子節點 結束
      以0[2]為Root作Heapify
      將0[14]與2[2]作Swap
      將0[14]與2[2]作Swap
      以0[2]為Root作Heapify
      1[3]最大 1[3]與0[2]做Swap
      1[2]沒有子節點 結束
      以0[2]為Root作Heapify
      將0[3]與1[2]作Swap
      將0[3]與1[2]作Swap
      以0[2]為Root作Heapify
      0[2]沒有子節點 結束
      以0[2]為Root作Heapify
      以0[2]為Root作Heapify
      0[2]沒有子節點 結束
      以0[2]為Root作Heapify
  • 時間複雜度(Time Complexity)
    • Best Case:Ο(n log n)
    • Worst Case:Ο(n log n)
    • Average Case:Ο(n log n)
    • 說明:
      • 建立MaxHeap: Ο(n)
      • 執行n-1次Delete Max:(n-1) × Ο(log n) = Ο( n log n)
      • Ο(n) + Ο( n log n) = Ο( n log n)
  • 空間複雜度(Space Complexity):Ο(1)
    • 原地置換(In-Place)
  • 穩定性(Stable/Unstable):不穩定(Unstable)
  • 演算法
    var swap = function(data, i, j){ 
        var tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    };
    
    // 令Root的左、右子樹皆符合Heap,僅Root不符合Heap,將樹調整為Max Heap
    var heapify = function(data, root, length){
        var leftChild = root*2 + 1;	    // Root的左子元素
        var rightChild = root*2 + 2;    // Root的右子元素
        var maxNode = -1;
    		
        // 找出root, leftChild, rightChild,值最大者(maNode)
        if(leftChild < length && (data[leftChild] > data[root]))
            maxNode = leftChild;
        else
            maxNode = root;	
        if(rightChild < length && (data[rightChild] > data[maxNode]))
            maxNode = rightChild;
    	
        // 如果值最大者不是root,則作swap及heapify
        if(maxNode != root){
            swap(data, root, maxNode);
            heapify(data, maxNode, length);
        }	
    };
    
    var heapSort = function(data){
        //將數列轉換成Max Heap
        for(var i = Math.floor( data.length/2)-1; i >= 0; i--){
            heapify(data, i, data.length);
        }	
    	
        //排序
        for(i = data.length - 1; i > 0; i--){
            swap(data, 0, i);
            heapify(data, 0, i);
        }
    };
    
    //執行
    var data = [92,38,59,57,14,52,19,69,23,84];
    heapSort(data);