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

二元樹的一種 ⇒ 每個父節點最多兩個子節點 · 堆積樹為完全二元樹(Complete Binary Tree)的一種 · 最小堆積(Min Heap) ：父節點的值小於子節點. 樹根(root)一定最所有節點的 ... [演算法(Algorithm)]堆積排序法(HeapSort) 堆積樹(HeapTree)：又叫堆、累堆 二元樹的一種每個父節點最多兩個子節點 堆積樹為完全二元樹(CompleteBinaryTree)的一種 最小堆積(MinHeap)：父節點的值小於子節點 樹根(root)一定最所有節點的最小值 最大堆積(MaxHeap)：父節點的值大於子節點 樹根(root)一定最所有節點的最大值 兄弟節點的大小不重要 堆積排序法為選擇排序法的改良 堆積排序作法 MaxHeap(Bottom-Up) MinHeap(Bottom-Up) Insert(Top-Down) 將數列轉換成MaxHeap 排序(最大堆積樹(MaxHeap)的樹根一定是最大值) 將樹根(最大值)與最後一個節點調換，將最後一個節點(原樹根)取出，並加入已排序數列 相當於對MaxHeapTree作DeleteMaxNode 對整棵樹重新調整為最大堆積樹調整後樹根為MaxNode 重複步驟1、2 將數列轉換成MinHeap 排序(最小堆積樹(MinHeap)的樹根一定是最小值) 將樹根(最小值)與最後一個節點調換，將最後一個節點(原樹根)取出，並加入已排序數列 相當於對MinHeapTree作DeleteMinNode 對整棵樹重新調整為最小堆積樹調整後樹根為MinNode 重複步驟1、2 將數列裡的數值依序加入HeapTree新加入的值為最後一個樹葉節點 每加入一個數值，則整棵樹重新調整為HeapTree 要由小排到大MinHeap 要由大排到小MaxHeap 取出:實作時一般是縮減HeapTree的範圍 取出前HeapTree陣列範圍為A[0-9] 取出最後一個樹枼節點後，HeapTree陣列範圍為A[0-8] 陣對映到二元樹 二元樹調整為MaxHeap 二元樹有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 以2[57]為Root進行Heapify Root[57]最大結束 以1[14]為Root進行Heapify 3[59]最大3[59]與Root[14]做Swap 3[14]沒有子節點結束 以0[38]為Root進行Heapify 1[59]最大1[59]與Root[38]做Swap 1[38]有子節點對1[38]作Heapify 以1[38]為Root進行Heapify 4[52]最大4[52]與Root[38]做Swap 4[38]沒有子節點結束 MaxHeap HeapSort(MaxHeap)圖解： 二元樹調整為MaxHeap 原始數列的二元樹 以4[45]為Root作Heapify 9[57]最大9[57]與4[45]做Swap 9[45]沒有子節點結束 以3[79]為Root作Heapify Root[79]最大結束 以2[92]為Root作Heapify Root[92]最大結束 以1[51]為Root作Heapify 3[79]最大3[79]與1[51]做Swap 3[51]有子節點對3[51]作Heapify 以3[51]為Root作Heapify 7[70]最大7[70]與3[51]做Swap 7[51]沒有子節點結束 以0[14]為Root作Heapify 2[92]最大2[92]與0[14]做Swap 2[14]有子節點對2[14]作Heapify 以2[14]為Root作Heapify 6[75]最大6[75]與2[14]做Swap 6[14]沒有子節點結束 MaxHeap 排序 MaxHeap 將0[92]與9[45]作Swap 以0[45]為Root作Heapify 1[79]最大1[79]與0[45]做Swap 1[45]有子節點對1[45]作Heapify 以1[45]為Root作Heapify 3[70]最大3[70]與1[45]做Swap 3[45]有子節點對3[45]作Heapify 以3[45]為Root作Heapify 7[51]最大7[51]與3[45]做Swap 7[45]沒有子節點結束 將0[79]與8[3]作Swap 以0[3]為Root作Heapify 2[75]最大2[75]與0[3]做Swap 2[3]有子節點對2[3]作Heapify 以2[3]為Root作Heapify 6[14]最大6[14]與2[3]做Swap 6[3]沒有子節點結束 將0[75]與7[45]作Swap 以0[45]為Root作Heapify 1[70]最大1[70]與0[45]做Swap 1[45]有子節點對1[45]作Heapify 以1[45]為Root作Heapify 4[57]最大4[57]與1[45]做Swap 4[45]沒有子節點結束 將0[70]與6[3]作Swap 以0[3]為Root作Heapify 1[57]最大1[57]與0[3]做Swap 1[3]有子節點對1[3]作Heapify 以1[3]為Root作Heapify 3[51]最大3[51]與1[3]做Swap 3[3]沒有子節點結束 將0[57]與5[2]作Swap 以0[2]為Root作Heapify 1[51]最大1[51]與0[2]做Swap 1[2]有子節點對1[2]作Heapify 以1[2]為Root作Heapify 4[45]最大4[45]與1[2]做Swap 4[2]沒有子節點結束 將0[51]與4[2]作Swap 以0[2]為Root作Heapify 1[45]最大1[45]與0[2]做Swap 1[2]有子節點對1[2]作Heapify 以1[2]為Root作Heapify 3[3]最大3[3]與1[2]做Swap 3[2]沒有子節點結束 將0[45]與3[2]作Swap 以0[2]為Root作Heapify 2[14]最大2[14]與0[2]做Swap 2[2]沒有子節點結束 將0[14]與2[2]作Swap 以0[2]為Root作Heapify 1[3]最大1[3]與0[2]做Swap 1[2]沒有子節點結束 將0[3]與1[2]作Swap 以0[2]為Root作Heapify 0[2]沒有子節點結束 以0[2]為Root作Heapify 0[2]沒有子節點結束 時間複雜度(TimeComplexity) BestCase：Ο(nlogn) WorstCase：Ο(nlogn) AverageCase：Ο(nlogn) 說明： 建立MaxHeap：Ο(n) 執行n-1次DeleteMax：(n-1)×Ο(logn)=Ο(nlogn) Ο(n)+Ο(nlogn)=Ο(nlogn) 空間複雜度(SpaceComplexity)：Ο(1) 原地置換(In-Place) 穩定性(Stable/Unstable)：不穩定(Unstable) 演算法 JS varswap=function(data,i,j){ vartmp=data[i]; data[i]=data[j]; data[j]=tmp; }; //令Root的左、右子樹皆符合Heap，僅Root不符合Heap，將樹調整為MaxHeap varheapify=function(data,root,length){ varleftChild=root*2+1; //Root的左子元素 varrightChild=root*2+2;//Root的右子元素 varmaxNode=-1; //找出root,leftChild,rightChild，值最大者(maNode) if(leftChilddata[root])) maxNode=leftChild; else maxNode=root; if(rightChilddata[maxNode])) maxNode=rightChild; //如果值最大者不是root，則作swap及heapify if(maxNode!=root){ swap(data,root,maxNode); heapify(data,maxNode,length); } }; varheapSort=function(data){ //將數列轉換成MaxHeap for(vari=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); } }; //執行 vardata=[92,38,59,57,14,52,19,69,23,84]; heapSort(data); Copyright©YehYeh.Allrightsreserved.