重学数据结构与算法-二叉堆
『22年09月19日』
图:斗西路口
二叉堆是一种特殊的二叉树,具有以下两个特性:
- 结构特性
它是一颗完全二叉树,表示树的每一层都有左侧和右侧子节点(除了最后一层的叶节点),并且最后一层的叶节点尽可能是左侧子节点 - 堆特性
不是最大堆就是最小堆。所有节点都大于等于(最大堆)或者小于等于(最小堆)它的左右子节点
下图展示了一些合法的二叉堆:
二叉堆的常见操作
- insert(value): 插入一个新节点
- extract(): 移除顶点,并返回顶点值
- findMininum(): 返回最小/大值,但不移除这个值
数据结构
怎么用 JavaScript 定义最小堆的数据结构?
通常,二叉树节点数据存储可以用链表也可以用数组,一般完全二叉树适合用数组来表示,因为这样就不需要存储子节点的指针,这样就可以节省存储空间,直接可以通过数组元素的位置计算出子节点的位置;其他类型的二叉树则不建议用数组来实现,因为并不是所有节点都遵循从左往右排列,所以节点的左右节点就容易为空,而造成数组空洞
所以可以用数组的方式来存储一颗完全二叉树,而节点之间有这个的关系:
对于给定位置 index 的节点:
- 它的左子节点位置为 2 x index +1
- 它的右子节点位置为 2 x index +2
- 它的父节点位置为(index-1)/ 2 向下取整
所以可以根据这个特性来构建二叉堆,以下以最小堆为例子:
- 用数组来存储节点
class MinHeap { constructor() { this.heap = []; } size() { return this.heap.length; } leftChild(index) { return 2 * index + 1; } rightChild(index) { return 2 * index + 2; } parent(index) { return Math.floor((index - 1) / 2); } }
- 插入算法
- 如果是第一个元素,则直接插入
- 如果已经不是第一个元素了,那么需要根据最小堆的规则(子节点必须永远大于等于父节点)调整二叉堆
insert(val) { if (this.size() === 0) { this.heap.push(val); } else { this.heap.push(val); this.siftUp(this.heap.length - 1); } } siftUp(index) { let parent = this.parent(index); while (this.heap[parent] > this.heap[index]) { const temp = this.heap[parent]; this.heap[parent] = this.heap[index]; this.heap[index] = temp; index = parent; parent = this.parent(parent); } }
- 移除最小值算法
- 最小堆的最小值就是数组的第一个元素
- 如果只有一个元素,则直接移除
- 如果不止一个元素,移除后要重新组建二叉堆(堆化),堆化的规则如下:
- 将最后一个元素移动到顶点
- 从顶点开始重新调整堆
extract() {
// shift with an empty array will return undefined
if (this.size() <= 2) {
return this.heap.shift();
} else {
const result = this.heap[0];
// 将最后一个元素移动顶点
this.heap[0] = this.heap.pop();
this.siftDown(0);
return result;
}
}
siftDown(index) {
let leftChild = this.leftChild(index);
let rightChild = this.rightChild(index);
if (leftChild >= this.size()) return;
let current = index;
// 找到子树的最小节点并替换
if (typeof this.heap[leftChild] !== undefined &&
this.heap[current] > this.heap[leftChild]) {
current = leftChild;
}
if (typeof this.heap[rightChild] !== undefined &&
this.heap[current] > this.heap[rightChild]) {
current = rightChild;
}
// 如果没有比顶点小的节点了,那就可停止堆化操作了
if (current !== index) {
const temp = this.heap[index];
this.heap[index] = this.heap[current];
this.heap[current] = temp;
this.siftDown(current);
}
}
- 找到最小值
- 最小值就是第一个元素,因为是最小堆
findMinimum() { return this.heap[0]; }
完整代码
See the Pen MinHeap by JinZhang (@jackzong) on CodePen.
二叉堆的应用