前言:
在js中是没有堆这个数据结构的，但我们可以用类和Array模拟一个堆
实现步骤:
· 在类里，声明一个数组，用来装元素。 · 主要方法：插入、删除堆顶、获取堆顶、获取堆大小。
CODE:（以最小堆为例）
class MinHeap {
constructor() {
this.heap
= []
}
swap(i1
, i2
) {
[this.heap
[i1
], this.heap
[i2
]] = [this.heap
[i2
], this.heap
[i1
]]
}
getParentIndex(i
) {
return (i
- 1) >> 1
}
getLeftIndex(i
) {
return i
* 2 + 1
}
getRightIndex(i
) {
return i
* 2 + 2
}
shiftUp(index
) {
if (index
=== 0) {
return
}
const parentIndex
= this.getParentIndex(index
)
if (this.heap
[parentIndex
] > this.heap
[index
]) {
this.swap(parentIndex
, index
);
this.shiftUp(parentIndex
)
}
}
shiftDown(index
) {
const leftIndex
= this.getLeftIndex(index
)
const rightIndex
= this.getRightIndex(index
)
if (this.heap
[leftIndex
] < this.heap
[index
]) {
this.swap(leftIndex
, index
)
this.shiftDown(leftIndex
)
}
if (this.heap
[rightIndex
] < this.heap
[index
]) {
this.swap(rightIndex
, index
)
this.shiftDown(rightIndex
)
}
}
insert(value
) {
this.heap
.push(value
)
this.shiftUp(this.heap
.length
- 1)
}
pop() {
this.heap
[0] = this.heap
.pop()
this.shiftDown(0)
}
peek() {
return this.heap
[0]
}
size() {
return this.heap
.length
}
}
const h
= new MinHeap()
h
.insert(3)
h
.insert(2)
h
.insert(1)
h
.pop()
console
.log(h
.peek())
console
.log(h
.size())
console
.log(h
)
Processed:
0.037, SQL:
10
