設計Max Heap1.基本架構

interface IHeap { get length(): number insert: (value: T) => void extract: () => T | undefined isEmpty: () => boolean buildHeap: (arr: T[]) => void}class Heap implements IHeap { private data: T[] = [] private size: number = 0 get length() { return this.size } private swap(i1: number, i2: number) { // 交換node位置 const temp = this.data[i1] this.data[i1] = this.data[i2] this.data[i2] = temp } private heapify_up() { } insert(value: T) { } private heapify_down() { } extract(): T | undefined { return undefined } isEmpty() { // 判斷Heap是否為空 return this.data.length === 0 } buildHeap(arr: T[]) { }}2.insert新增node至heap中，透過上濾(percolate up)方式與parent node做比較進行互換，將insert node放至相對應合適的位置(index)中。

private heapify_up() { // 2.獲取前步驟push至data中的index let currentIndex = this.data.length - 1 // 3.使用while循環，循環至root為止 while (Math.floor((currentIndex - 1) / 2) >= 0) { // 4.套用公式Math.floor((i - 1) / 2)找到parent node const parentIndex = Math.floor((currentIndex - 1) / 2) // 5.當parent node的value >= current node時直接break停止上濾 if (this.data[parentIndex] >= this.data[currentIndex]) break // 6.不符合步驟五的情況下，parent/current的value做交換 this.swap(currentIndex, parentIndex) // 7.交換完後當前的current node會是在原先parent node的index，所以這裡要改變currentIndex變數的值 currentIndex = parentIndex } } insert(value: T) { // 1.將value push至data中 this.data.push(value) this.size++ this.heapify_up() }3.extract將heap中的最大值移除，透過下濾(percolate down)方式將left/right node做比較進行互換。

private heapify_down(index: number) { let currentIndex = index // 6.確認當前node至少還有left node才能繼續執行下濾 while (currentIndex * 2 + 1 < this.data.length) { // 7.套用 (i*2)+1公式 const leftIndex = currentIndex * 2 + 1 // 8.套用 (i*2)+2公式 const rightIndex = currentIndex * 2 + 2 // 9.後續要比較left/right哪一個node較大，預設先設置left，因為在步驟六中至少能確定是有left node let largeIndex = leftIndex // 10.確認有right node且right node比left node大時，將largeIndex替換成rightIndex if (rightIndex < this.data.length && this.data[rightIndex] > this.data[leftIndex]) largeIndex = rightIndex // 11.currentIndex若比largeIndex的node大時，直接break停止while循環 if (this.data[currentIndex] >= this.data[largeIndex]) break // 12.currentNode與largetNode(left/right)進行交換 this.swap(currentIndex, largeIndex) // 13.前步驟交換的關係，所以currentIndex位置會是原先largeIndex位置 currentIndex = largeIndex } } extract(): T | undefined { if (this.data.length === 0) { // 1.當data中沒有任何node直接retrun return } else if (this.data.length === 1) { // 2.當data中只有一個node直接移除並retrun 移除的node this.size-- return this.data.pop()! } else { // 3.當data中有兩個以上node時，先把index為0的node保存起來，且能確定是最大的node const topValue = this.data[0] // 4.並將data中最後一個node放入data[0]，主要就是要透過該node進行下濾操作 this.data[0] = this.data.pop()! this.size-- // 5.調用下濾方法，因為是下濾所以會是從最前面(0)index開始 this.heapify_down(0) return topValue } }extract流程圖

Press enter or click to view image in full size4.buildHeap將一個無序Array轉換成Max Heap，透過for循環從最後一個非leaf node index循環至第一個，且每次循環時掉用下濾(percolate down)方法。

buildHeap(arr: T[]) { this.data = arr this.size = this.data.length // 1.套用 Math.floor(length / 2)公式 const lastNodeIndex = Math.floor(this.length / 2) // 2.從最後一個非leaf node index循環至第一個 for (let i = lastNodeIndex; i >= 0; i--) { // 3.掉用下濾方法 this.heapify_down(i) }}5.完整程式碼

interface IHeap { get length(): number insert: (value: T) => void extract: () => T | undefined isEmpty: () => boolean buildHeap: (arr: T[]) => void}class Heap implements IHeap { private data: T[] = [] private size: number = 0 get length() { return this.size } private swap(i1: number, i2: number) { const temp = this.data[i1] this.data[i1] = this.data[i2] this.data[i2] = temp } private heapify_up() { let currentIndex = this.data.length - 1 while (Math.floor((currentIndex - 1) / 2) >= 0) { const parentIndex = Math.floor((currentIndex - 1) / 2) if (this.data[parentIndex] >= this.data[currentIndex]) break this.swap(currentIndex, parentIndex) currentIndex = parentIndex } } insert(value: T) { this.data.push(value) this.size++ this.heapify_up() } private heapify_down(index: number) { let currentIndex = index while (currentIndex * 2 + 1 < this.data.length) { const leftIndex = currentIndex * 2 + 1 const rightIndex = currentIndex * 2 + 2 let largeIndex = leftIndex if (rightIndex < this.data.length && this.data[rightIndex] > this.data[leftIndex]) largeIndex = rightIndex if (this.data[currentIndex] >= this.data[largeIndex]) break this.swap(currentIndex, largeIndex) currentIndex = largeIndex } } extract(): T | undefined { if (this.data.length === 0) { return } else if (this.data.length === 1) { this.size-- return this.data.pop() } else { const topValue = this.data[0] this.data[0] = this.data.pop()! this.size-- this.heapify_down(0) return topValue } } isEmpty() { return this.data.length === 0 } buildHeap(arr: T[]) { this.data = arr this.size = this.data.length const lastNodeIndex = Math.floor(this.length / 2 - 1) for (let i = lastNodeIndex; i >= 0; i--) { this.heapify_down(i) } }}