>[success] # 使用堆進行排序 ~~~ 1.堆兩種形式，一種是最大堆，一種是最小堆，我們可以利用這個特性對數組進行快速排序 ，這樣排序的時間復雜度'O(nlogn)' 2.用堆進行排序當然需要兩步，第一步是吧數組中雜亂無章的數據先變成'堆'，這個過程時間復雜度 為'O(n)',當整個'堆'建立完成后，需要對其排序，樹排序是根據樹的高度，堆的好處就是因為定義概念 將整體高度和數組長度相比是更短所用的時間也是更少的'O(nlogn)',因此這個建堆和排序過程我們可以 看做成'O(nlogn)' 3.用最大堆得到一個升序排列的數組（從最小到最大）。要這個數組按降序排列，可以用最小堆代替。 ~~~ >[info] ## 代碼實現 ~~~ const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0 }; function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; } function reverseCompare(compareFn) { return (a, b) => compareFn(b, a); } function swap(array, a, b) { /* const temp = array[a]; array[a] = array[b]; array[b] = temp; */ [array[a], array[b]] = [array[b], array[a]]; } // 將數組變成堆結構，這是一個創建堆的過程 function heapify(array, index, heapSize, compareFn) { let largest = index; const left = (2 * index) + 1; const right = (2 * index) + 2; if (left < heapSize && compareFn(array[left], array[index]) > 0) { largest = left; } if (right < heapSize && compareFn(array[right], array[largest]) > 0) { largest = right; } if (largest !== index) { swap(array, index, largest); heapify(array, largest, heapSize, compareFn); } } // 創建調用的方法 function buildMaxHeap(array, compareFn) { for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) { heapify(array, i, array.length, compareFn); } return array; } // 將堆進行排序 function heapSort(array, compareFn = defaultCompare) { let heapSize = array.length; // 用數組創建一個最大堆用作源數據。 buildMaxHeap(array, compareFn); while (heapSize > 1) { // 在創建最大堆后，最大的值會被存儲在堆的第一個位置。我們要將它替換為堆的最后一個 // 值，將堆的大小減 1。 swap(array, 0, --heapSize); // 們將堆的根節點下移并重復步驟 2 直到堆的大小為 1 heapify(array, 0, heapSize, compareFn); } return array; } ~~~