[演算法(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
以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]沒有子節點結束Max Heap
- Heap Sort(Max Heap)圖解:
- 二元樹調整為Max Heap
原始數列的二元樹以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]沒有子節點 結束Max Heap
- 排序
Max Heap將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]沒有子節點 結束
- 二元樹調整為Max Heap
- 時間複雜度(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);