堆(二叉堆)
是什么
堆（heap）是计算机科学中一类特殊的数据结构统称。通常是一个可被看做一棵树的数组对象。
最小堆
当一个数据结构满足：
- 任意节点 P 和 C，若 P 是 C 的父节点，那么一定有 P 的值小于 C 的值。
- 总是一棵完全二叉树
则称这个数据结构为最小堆。
最大堆
当一个数据结构满足：
- 任意节点 P 和 C，若 P 是 C 的父节点，那么一定有 P 的值大于 C 的值。
- 总是一棵完全二叉树
则称这个数据结构为最大堆。
怎么做
最小堆
插入原理：
- heap 为空时，键值 10 作为根节点
- 23 > 10，可作为 10 的 子节点
- 36 > 10，可作为 10 的 子节点
- 18 < 23，不可作为 23 的子节点，调换 23 与 18 的位置。18 > 23 符合条件，构造完成
删除原理：
最小堆删除根节点时，将最后一位移动至根节点，依次比较根节点与子节点大小，若根节点大于子节点，则调换位置，重复至比较完成。
创建最小堆：
class MinHeap {
constructor() {
this.heap = []
}
// 交换位置
swap(i1, i2) {
const temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
// 获取上节点
getParentIndex(i) {
// 向前移一位的操作
return Math.floor((i - 1) / 2) // return (i - 1) >> 1 可以通过二进制向前移一位的操作实现除2取整的
}
// 获取左节点
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.insert(4)
h.insert(5)
h.insert(6)
h.insert(7)
h.pop() // [2, 4, 3, 7, 5, 6]
// console.log(h.peek())
// console.log(h.size())
console.log(h)
最大堆
最大堆和最小堆的算法一模一样，不同的是要把所有的大于换成小于的比较。
class MinHeap {
constructor() {
this.heap = []
}
swap(i1, i2) {
const temp = this.heap[i1]
this.heap[i1] = this.heap[i2]
this.heap[i2] = temp
}
getParentIndex(i) {
// 如下写，显得比较臃肿
return Math.floor((i - 1) / 2)
// 可以通过二进制向前移一位的操作
// 实现除2取整的
// 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)
}
}
pop() {
this.heap[0] = this.heap.pop()
this.shiftDown(0)
}
insert(value) {
this.heap.push(value)
this.shiftUp(this.heap.length - 1)
}
// 获取堆顶：返回数组的头部。
peek() {
return this.heap[0]
}
// 获取堆的大小：返回数组的长度。
size() {
return this.heap.length
}
}
使用方法：
const h = new MinHeap()
h.insert(4)
h.insert(3)
h.insert(2)
h.insert(1)
h.pop()
// console.log(h.peek())
// console.log(h.size())
console.log(h)