最小堆
最小堆类 - 锐客网 【最小堆】最小堆类
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 = https://www.it610.com/article/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())
文章图片
推荐阅读
- JS中的各种宽高度定义及其应用
- 祖母走了
- 唯独你最得我意
- 人生感悟记＃环境仪器宋庆国成长记＃072
- 危险也是机会
- “精神病患者”的角度问题
- 对抗抑郁最好的方法
- 放下心中的偶像包袱吧
- 怎样用黑谜速冻膜去黑头，|怎样用黑谜速冻膜去黑头， 最有效的去黑头的方法看这!
- 拉黑家人一整年之后，以为会快乐，最后却抑郁症！！