带你读《图解算法小抄》八、堆(1)https://developer.aliyun.com/article/1348205?groupCode=tech_library
2. 最大堆
class MaxHeap { constructor() { this.heap = []; } // 获取父节点的索引 getParentIndex(index) { return Math.floor((index - 1) / 2); } // 获取左子节点的索引 getLeftChildIndex(index) { return 2 * index + 1; } // 获取右子节点的索引 getRightChildIndex(index) { return 2 * index + 2; } // 交换元素位置 swap(index1, index2) { [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]; } // 上移操作(向上调整堆) siftUp(index) { if (index === 0) { return; } const parentIndex = this.getParentIndex(index); if (this.heap[parentIndex] < this.heap[index]) { this.swap(parentIndex, index); this.siftUp(parentIndex); } } // 下移操作(向下调整堆) siftDown(index) { const leftChildIndex = this.getLeftChildIndex(index); const rightChildIndex = this.getRightChildIndex(index); let maxIndex = index; if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[maxIndex]) { maxIndex = leftChildIndex; } if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[maxIndex]) { maxIndex = rightChildIndex; } if (maxIndex !== index) { this.swap(index, maxIndex); this.siftDown(maxIndex); } } // 插入元素到堆中 insert(value) { this.heap.push(value); this.siftUp(this.heap.length - 1); } // 获取堆顶元素(最大值) peek() { if (this.heap.length === 0) { return null; } return this.heap[0]; } // 删除堆顶元素(最大值) remove() { if (this.heap.length === 0) { return null; } const maxValue = this.heap[0]; const lastValue = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = lastValue; this.siftDown(0); } return maxValue; } // 获取堆的大小 size() { return this.heap.length; }}
3. 参考
∙ YouTube