21 【算法】在JS中实现Heap堆及堆操作
什么是Heap？
Heap是一种满足堆属性的专用基于树的数据结构。在一个堆中，对于任何给定节点（除了根节点），该节点的值始终根据其父节点排序。
这种排序可以是以下两种类型：
- **最大堆：**在最大堆中，对于除根节点外的每个节点，节点的值最多等于其父节点的值。这意味着最大的元素位于根节点，随着向下遍历树，元素变得更小。简单来说，所有子节点都必须小于其父节点。
- **最小堆：**在最小堆中，对于除根节点外的每个节点，节点的值至少等于其父节点的值。这意味着最小的元素位于根节点，随着向下遍历树，元素变得更大。
堆的特点
堆还是一颗完全二叉树，这意味着树的所有层级都是完全填充的，如果最后一层不完整，节点会从左到右填充。
优先队列经常使用二叉堆实现，尽管这不是实现的唯一方式。当我们希望根据某些优先级值对队列进行排序时，它用于排序队列。
这意味着每个元素都有一定的优先级。元素的优先级决定了元素从优先队列中删除的顺序。
堆的实现
实现堆最简单的方法是不使用二叉树，而是使用一个数组数据结构。这是因为它们是完全二叉树。
通过使用数组，我们还确保树中没有间隙（除了最后一层必须从左到右填充），允许一种紧凑的表示，而不会浪费任何空间。
如果你仔细观察这个二叉堆，你会注意到每个节点下面都有一个索引，表示它在数组表示中的索引。
如果我们切换到数组视图，这就是我们的二叉堆的样子：
我们使用基于1的索引，这意味着我们不计算数组中的第0个项，根节点开始于索引1。在这种情况下，如果一个节点在数组中的索引为 i：
- 如果左子节点存在，则其索引为2*i。
- 如果右子节点存在，则其索引为2*i+1。
- 如果其父节点存在且
i不是1（根节点），则其父节点索引为 ⌊i/2⌋。
这意味着根节点从 arr[1] 开始，左节点是 arr[2]，右节点是 arr[3] 等等。
这种表示利用了完全二叉树的属性，允许在不需要基于指针/引用的树节点结构之间轻松导航到父节点和子节点。
堆操作
堆的主要操作包括插入元素，提取最大/最小元素以及堆化以维护堆属性。
我建议查看这些操作的可视化表示 以更好地理解它们。
插入
class Heap {
constructor() {
// 在这里使用 null 初始化堆以使用基于1的索引
this.heap = [null];
}
// 将新值插入堆中
insert(value) {
this.heap.push(value);
this.heapifyUp(this.heap.length - 1);
}
// 在插入后堆化以维护堆属性
heapifyUp(index) {
while (index > 1 && this.heap[Math.floor(index / 2)] < this.heap[index]) {
this.swap(Math.floor(index / 2), index);
index = Math.floor(index / 2);
}
}
// 交换堆中的两个值
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
}
这个Heap类的insert方法将一个新值添加到堆中，然后通过重新排列元素来确保堆保持其属性。以下是它的工作原理：
- 将新值添加到数组（
this.heap）的末尾。这一步保持了树的完整性，意味着树的所有层级都是完全填充的，除了可能未完整的最后一层，这一层会从左到右填充。 - 然后，使用新添加值的索引调用
heapifyUp方法，以维护堆属性。
heapifyUp是如何工作的：
- 在当前节点有父节点且违反堆属性时（即，对于最大堆，当前节点大于其父节点），将其与其父节点交换。
- 继续这个过程直到堆属性被恢复（当前节点不再大于其父节点或者成为根节点）。
insert方法的最坏时间复杂度为O(log n)，因为新添加的元素可能需要在树的底部到顶部的每一级进行比较并可能交换以维护堆属性。
提取
提取是从堆中删除根元素。如果我们只想查看堆的顶部项（最小或最大项），我们可以以O(1)的时间复杂度在第一个索引this.heap[1]下访问它。
class Heap {
constructor() {
this.heap = [null];
}
// 移除并返回堆中的最大值
extractMax() {
if (this.heap.length < 2) return null; // 堆为空
const maxValue = this.heap[1];
this.heap[1] = this.heap.pop(); // 将最后一个值移动到根部
this.heapifyDown(1);
return maxValue;
}
// 在提取后堆化以维护堆属性
heapifyDown(index) {
let largest = index;
const left = 2 * index;
const right = 2 * index + 1;
if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
largest = left;
}
if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
largest = right;
}
if (largest !== index) {
this.swap(index, largest);
this.heapifyDown(largest);
}
}
// 交换堆中的两个值
swap(index1, index2) {
[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
}
}
extractMax方法从最大堆中移除并返回最大值。以下是它的工作原理，一步一步地说明，以及其时间复杂度：
- 检查堆是否为空： 如果堆包含少于两个元素（考虑到第一个元素是
null用于基于1的索引），意味着堆为空，方法返回null。 - 移除最大值： 最大堆中的最大值始终位于根部，即
this.heap[1]。此值存储在maxValue中以便稍后返回。 - 重新排序堆： 将堆中的最后一个元素移动到根的位置（
this.heap[1]）。此操作保持了二叉树的完整性，但可能会违反堆属性。为了恢复堆属性，从根开始调用heapifyDown。 - 返回
maxValue： 最后，方法返回原本在堆根部的值，即堆的最大值。
heapifyDown如何工作：
heapifyDown通过将当前节点与其左右子节点进行比较，以查找其中最大的值，从而保持堆属性。- 如果当前节点不是最大值，它会与其子节点中最大的值交换。这可能会违反进行交换的子树的堆属性，因此会递归调用
heapifyDown以进行交换的子节点的索引。 - 它会继续直到整个堆的堆属性恢复正常，即当前节点大于其子节点或没有子节点。
extractMax的最坏时间复杂度为O(log n)，因为必须在每个树层级执行比较和交换以在移除最大元素后恢复堆属性。
堆化
heapify操作用于将任意数组转换为堆。这通过从最后一个非叶节点到根应用heapifyDown完成。
class Heap {
constructor() {
this.heap = [null];
}
// 从未排序的数组构建堆
buildHeap(arr) {
this.heap = [null, ...arr]; // 重置堆并设置值
const startIdx = Math.floor(this.heap.length / 2);
for (let i = startIdx; i >= 1; i--) {
this.heapifyDown(i);
}
}
heapifyDown(index) {
// 与之前相同
}
}
buildHeap如何工作：
- 该方法首先将
heap属性设置为一个新数组，该数组以null开头（用于基于1的索引），然后是输入数组arr的元素。 - 它计算堆化过程的起始索引，即最后一个非叶节点的索引，为
Math.floor(this.heap.length / 2)。这是因为树中所有节点在此之后都是叶节点，它们已经满足堆属性。 - 它从起始索引倒序遍历到堆的根（索引为1），为每个节点调用
heapifyDown。这个过程确保为每个节点建立堆属性，有效地将未排序的数组转换为堆。
从未排序的数组构建堆的时间复杂度为O(n)，其中n是数组中的元素数量。一开始可能看起来有些反直觉，因为heapifyDown的时间复杂度是O(log n)，并在循环中被调用。
然而，并不是所有对heapifyDown的调用都会沿着树的完整高度。对于接近树底部的节点，需要较短的路径进行调整，并且随着向上移动树，每个级别的节点数量翻倍，平衡了成本。平均在所有元素上进行平均后，从未排序的数组构建堆的时间复杂度是线性的。