[toc]
# 介绍
堆（Heap）是一种特殊的二叉树：
1. 堆是一个完全二叉树
2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中的每个节点的值
# 分类
堆分为两种：`大顶堆` 和 `小顶堆` 。
* 大顶堆：父顶点的值大于所有子顶点的值。
* 小顶堆：父顶点的值小于所有子顶点的值。
大顶堆：
小顶堆：
# 存储
堆是一种二叉树，有两种存储方式：
- 数组
- 链表
堆是一种完全二叉树，而完全二叉树使用 `数组` 存储比较合适。
当以数组保存二叉树时有以下几个重要公式。
1. 对于下标为 i 节点（子节点）
左子节点下标：2i+1
右子节点下标：2i+2
2. 对于下标为 i 的节点（父节点）
父节点下标：Math.floor( (i-1) / 2 )
3. 最后一个非叶子节点的节点的下标
Math.floor(len/2) - 1
# 应用场景
1. 排序 ---》 堆排序（时间复杂度：O(nlogn)
2. 优先队列（优先级高的放到前面）
# 操作
二叉堆的操作有三种：
- 插入节点
- 删除节点
- 构建二叉堆
## 插入节点
当向二叉堆中插入新节点时的操作：
1. 将新节点先放到 `最后`
2. 然后依次和父节点比较，然后 `上浮`
如，插入0：
1. 插入到最后
2. 和父节点比较并上浮
3. 和父节点比较并上浮
4. 继续比较上浮
## 删除节点
删除节点时，一般就是删除堆是根节点，过程和插入节点正好相反：
1. 删除顶节点
2. 将最后一个节点拿到父节点
3. 和子节点比较并 `下沉`
比如，删除 1
1. 删除节点
2. 将最后一个节点临时拿到根节点的位置
3. 和左右子节点比较，让最小的节点上来，它下沉
4. 继续和子节点比较并下沉
## 构建二叉堆
[排序](%E6%8E%92%E5%BA%8F.md)从最后一个 `非叶子节点 Math.floor(数组长度/2)-1` 开始比较并 （大/小）上浮。
1. 比较有以下堆
2. 从最后一个非叶子节点开始比较
# 代码实现
~~~
// 小顶堆
class SmallHeap {
constructor() {
// 初始化一个保存数据的数组
this.arr = []
}
// 向堆中放数据
push(data) {
// 1. 先将数据放到堆尾
this.arr.push(data)
// 2. 上浮（依次和父节点进行比较）
// 2.1 获取当前这个新元素的下标
let current = this.arr.length - 1
// 2.2 父元素的下标
let parent = Math.floor((current - 1) / 2)
// 2.3 循环一直找父节点
while (parent >= 0) {
// 2.4 和父节点比较
if (this.arr[current] < this.arr[parent]) {
// 2.5 交换
[this.arr[current], this.arr[parent]] = [this.arr[parent], this.arr[current]]
// 2.6 当前节点的下标变成父节点的下标
current = parent
// 2.7 重新计算新的父节点
parent = Math.floor((current - 1) / 2)
} else {
// 2.8 如果当前节点大就退出循环
break
}
}
}
// 弹出堆顶元素
pop() {
// 1. 获取堆顶元素的值
let value = this.arr[0]
// 2. 获取数组中最后一个元素的值，并将这个值从数组中删除
let lastValue = this.arr.pop()
// 3. 最后一个值替换第1个元素
this.arr[0] = lastValue
// 4. 和子节点比较然后进行下沉
// 4.1 当前节点的下标
let current = 0
// 4.2 左、右子节点的下标
let left = 2 * current + 1
let right = 2 * current + 2
let smallest = 0 // 最小元素的下标
// 如果有子节点就向下比较
while (left < this.arr.length) {
// 4.3 比左子节点大
if (this.arr[current] > this.arr[left]) {
// 左子节点和右子节点的大小
if (this.arr[left] > this.arr[right]) {
// 右边最小
smallest = right
} else {
// 左边最小
smallest = left
}
} else {
// 当前节点小于左子节点
// 判断和右子节点的大小
if (this.arr[current] <= this.arr[right]) {
// 退出循环
break
} else {
smallest = right
}
}
// 最小元素的下标和当前元素下标是否相等
if (current === smallest) {
break
} else {
// 当前元素和最小元素进行交换
[this.arr[current], this.arr[smallest]] = [this.arr[smallest], this.arr[current]]
// 修改相关下标
current = smallest // 当前下标变成交换之后最小的下标
// 重新计算左右子节点下标
left = 2 * current + 1
right = 2 * current + 2
}
}
return value
}
}
let smH = new SmallHeap()
smH.push(10)
smH.push(5)
smH.push(2)
smH.push(8)
smH.push(1)
smH.push(4)
console.log(smH.arr)
console.log(smH.pop())
console.log(smH.arr)
~~~
