<!DOCTYPE html><html><head> <meta charset="UTF-8"> <title>最小堆类</title></head><body> <p>最小堆类</p> <script src="./index.js"></script></body></html>
class MinHeap{ constructor() { this.heap = [] } // 获取堆 getHeap() { return this.heap } // 获取元素父元素下标 getParentIndex(i) { return (i - 1) >> 1 } // 获取元素左孩子下标 getLeftIndex(index) { return index * 2 + 1 } // 获取元素的右孩子下标 getRightIndex(index) { return index * 2 + 2 } // 替换值 swap(i1, i2) { const temp = this.heap[i1] this.heap[i1] = this.heap[i2] this.heap[i2] = temp } // 向上调整 shiftUp(index) { // 元素下标为0，进行调整 if (index === 0) return // 获取父元素下标 const parentIndex = this.getParentIndex(index) // 如果以后元素比父元素小，替换值 if (this.heap[parentIndex] > this.heap[index]) { this.swap(index, parentIndex) // 递归 this.shiftUp(parentIndex) } } // 向下调整 shiftDown(index) { // 获取左右孩子下标 const left = this.getLeftIndex(index) const right = this.getRightIndex(index) // 如果左孩子比以后节点小，替换值 if (this.heap[index] > this.heap[left]) { this.swap(index, left) // 递归 this.shiftDown(left) } // 如果右孩子比以后节点小，替换值 if (this.heap[index] > this.heap[right]) { this.swap(index, right) // 递归 this.shiftDown(right) } } // 向堆中插入元素 insert(n) { this.heap.push(n) // 从堆尾元素开始向上调整堆，使其成为最小堆 this.shiftUp(this.heap.length - 1) } // 删除堆顶 pop() { // 将堆顶元素与堆尾元素替换 this.swap(0, this.heap.length - 1) // 保留堆顶元素，作为函数返回值 const value = this.heap.pop() // 从堆顶元素开始向下调整堆，使其成为最小堆 this.shiftDown(0) // 返回删除的堆顶元素 return value }}const h = new MinHeap()h.insert(9)h.insert(6)h.insert(7)h.insert(4)h.insert(3)h.insert(5)h.insert(2)h.insert(8)h.insert(1)console.log('heap', h.getHeap())console.log('pop', h.pop())console.log('heap', h.getHeap())console.log('pop', h.pop())console.log('heap', h.getHeap())console.log('pop', h.pop())console.log('heap', h.getHeap())console.log('pop', h.pop())console.log('heap', h.getHeap())