>[success] # 創建堆 ~~~ 1.創建堆類的方法說明 1.1.getLeftIndex -- 獲取左側節點對應數組實際位置 1.2.getRightIndex -- 獲取右側節點對應數組實際位置 1.3.getParentIndex -- 獲取父節點對應數組實際位置 1.4.size -- 堆的大小 1.5.isEmpty -- 堆是否為空 1.6.clear -- 清除堆 1.7.findMinimum -- 求出堆的最小值這里指是最小堆類，最大堆最小堆根接地是對應最大值最小值 1.8.insert -- 堆中插入數據 1.9.siftUp -- 插入數據的比較方法 1.10.extract -- 移除最小堆的最小值 1.11.siftDown -- 從上向下比較進行交換找到最小值 1.12.heapify -- 堆化一個數組 ~~~ >[info] ## 代碼實現 -- 最小堆 ~~~ 1.'siftUp' 上移操作方法說明，當往堆中插入一個元素后，將元素插入數組末尾，依次讓該元素和其父節點 進行比較，根據創建的大小堆來決定是否和父節點更換位置 -- '當做堆的插入時候用這個思想' 2.'siftDown' 從上向下比較進行交換找到最小值 -- '當做刪除的時候用這個思想，這里的刪除指的是刪除最大或最小' 3.'heapify' 數組堆化，實際只要將非葉子節點，進行堆化后自然就形成了堆，因此循環是二分之一 ~~~ * siftUp 圖解  * siftDown 圖解  * heapify 圖解 ~~~ 1.二叉堆用的是數組的形式，我們想把一個數組變成堆，最簡單的方法，我們循環這個數組一次通過siftUp 插入數組中的 數據 2.第二種就是將整個數組先看成樹，然后將樹這個樹 拆分成小樹，這些小樹通過'siftDown'進行重新排序， 這里要說明的是我們'siftDown'是一個抽離方法，他其實是根節點和下面的子節點進行比較 3.堆的長度的一半是個個根節點，我們有這些數據分成小樹，這些小的樹堆化后就會形成大的樹 ~~~   ~~~ 1.'說明': 首先我們針對的是二叉堆操作，其次我們一直遵循'siftUp'這種插入規則所以依次比較父節點是沒問題的 2.'siftUp' -- 對應插入 3.'siftDown' -- 對應的是刪除。因為二叉堆要不就最大堆，要不就是最小堆，這里的刪除指的是刪除堆頂 ~~~ ~~~ 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]]; } class MinHeap { constructor(compareFn = defaultCompare) { this.compareFn = compareFn; this.heap = [] } // 計算左側節點數在數組對應位置 getLeftIndex(index) { return (2 * index) + 1 } // 計算右側節點數組對應位置 getRightIndex(index) { return (2 * index) + 2 } // 計算父節點位置 getParentIndex(index) { if (index === 0) { return undefined } return Math.floor((index - 1) / 2) } // 計算堆得大小 size() { return this.heap.length } // 判斷是否為空 isEmpty() { return this.size() <= 0 } // 清空堆 clear() { this.heap = [] } // 找到堆的最小值，因為這是最小堆，所以根節點是最小的 findMinimum() { return this.isEmpty ? undefined : this.heap[0] } // 插入 insert(value) { // 插入的時候判斷不能插入為空 if (value != null) { const index = this.heap.length this.heap.push(value) this.siftUp(index) return true } return false } // 插入數據 siftUp(index) { let parent = this.getParentIndex(index) // 從下向上和自己的父節點進行比較，來換彼此位置 while (index > 0 && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN) { swap(this.heap, parent, index); index = parent parent = this.getParentIndex(index) } } // 移除最小堆的最小值 extract() { // 分情況討論，當前堆數據空，當前堆數據只有一個，當前堆數據有多個 if (this.isEmpty()) { return undefined } if (this.size() === 1) { return this.heap.shift() } const romevedValue = this.heap[0] // 并且把數組最后一項移到頭部 this.heap[0] = this.heap.pop() // 進行比較換位選出實際最小的為數組的第一位 this.siftDown(0) return romevedValue } // 從上向下比較進行交換找到最小值 siftDown(index) { /* 1.思路就是知道當前值 和當前值和葉子節點關系大小，因為這是二叉樹 所以也就是相當于比較左右葉子節點先獲取，當前值 即當前值左右葉子節點 在數組中的位置 */ let element = index // 當前值的位置 let left = this.getLeftIndex(index) // 當期值的左節點 let right = this.getRightIndex(index) // 當前值的右節點 const size = this.size(); /* 1.比較的思路，因為在比較過程中會不停的更換兩個節點的位置，即到最 后節點的位置就將是數組的最后一位，如果比較的過程中已經是最后一位了 說明樹已經全部比較完畢 2.當然也要比較當前節點和左右節點的關系 */ if (left < size && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN) { element = left; } if (right < size && this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN) { element = right; } // 什么繼續遞歸？當 index 也就無法在改變element 值的時候，即已經 // 到了數組末端 index 和 element 相等就無非遞歸，反之就繼續遞歸 if (index !== element) { swap(this.heap, index, element); this.siftDown(element); } } // 堆化數組 ，查分成小的組合成大 heapify(array) { if (array) { this.heap = array; } const maxIndex = Math.floor(this.size() / 2) - 1; for (let i = 0; i <= maxIndex; i++) { this.siftDown(i); } return this.heap; } getAsArray() { return this.heap; } } let heap = new MinHeap(); heap.insert(2); heap.insert(3); heap.insert(4); heap.insert(5); heap.insert(2); console.log(heap.getAsArray()); console.log(heap.heapify([2, 5, 7, 8, 9, 1, 4, 3])); ~~~ >[info] ## 代碼實現 -- 最大堆 ~~~ class MaxHeap extends MinHeap { constructor(compareFn = defaultCompare) { super(compareFn); this.compareFn = compareFn; this.compareFn = reverseCompare(compareFn); } } ~~~