<!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())