【数据结构与算法】堆

定义

堆是是一个完全二叉树，其中每个节点的值都大于等于或小于等于其子节点的值。这取决于是最大堆还是最小堆。

小根堆：每个根都小于子节点。
大根堆：每个根都大于子节点。

以下部分图例说明来源：【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili

基本操作

堆的上滤（heapify up）和下滤（heapify down）是用于维护堆的性质的两种重要操作，它们通常在插入和删除元素时被调用。

上滤（Heapify Up）

上滤是指将新插入的元素从底部向上移动，直到满足堆的性质为止。复杂度：O(logn)

当新元素被插入到堆的末尾时，它可能破坏了堆的性质，因为它可能比其父节点更大（对于最大堆）或更小（对于最小堆）。

上滤操作会持续比较新插入节点与其父节点的值，如果满足堆的性质，则停止；否则，交换它们的位置，然后继续向上比较，直到满足堆的性质。

上滤的步骤：

比较新插入节点与其父节点的值。
如果新插入节点的值比父节点的值大（对于最大堆）或小（对于最小堆），则交换它们的位置。
继续向上重复上述步骤，直到满足堆的性质或到达堆的根节点。

JavaScript 实现上滤的示例：

function heapifyUp(heap, index) {let parentIndex = Math.floor((index - 1) / 2);while (index > 0 && heap[index] > heap[parentIndex]) { // 最大堆的情况，若为最小堆则将判断条件改为 heap[index] < heap[parentIndex][heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]]; // 交换节点值index = parentIndex;parentIndex = Math.floor((index - 1) / 2);}
}

下滤（Heapify Down）

下滤是指将堆顶元素从上向下移动，直到满足堆的性质为止。复杂度：O(logn)

当堆顶元素被删除或替换时，堆的性质可能被破坏，因为新的堆顶元素可能不再满足堆的性质。

下滤操作会持续比较堆顶元素与其子节点的值，如果满足堆的性质，则停止；否则，选择较大（对于最大堆）或较小（对于最小堆）的子节点进行交换，然后继续向下比较，直到满足堆的性质或到达堆的叶子节点。

下滤的步骤：

比较堆顶元素与其子节点的值，选择较大（对于最大堆）或较小（对于最小堆）的子节点。
如果堆顶元素比子节点的值小（对于最大堆）或大（对于最小堆），则交换它们的位置。
继续向下重复上述步骤，直到满足堆的性质或到达堆的叶子节点。

JavaScript 实现下滤的示例：

function heapifyDown(heap, index, size) {let largest = index;const left = 2 * index + 1;const right = 2 * index + 2;if (left < size && heap[left] > heap[largest]) { // 最大堆的情况，若为最小堆则将判断条件改为 heap[left] < heap[largest]largest = left;}if (right < size && heap[right] > heap[largest]) { // 最大堆的情况，若为最小堆则将判断条件改为 heap[right] < heap[largest]largest = right;}if (largest !== index) {[heap[index], heap[largest]] = [heap[largest], heap[index]]; // 交换节点值heapifyDown(heap, largest, size);}
}

在堆中，常见的基本操作包括：

插入节点： 将新节点插入到堆的末尾，然后通过一系列比较与交换操作，将它与其父节点比较并移动，直到满足堆的性质为止。
删除节点： 通常是删除堆顶元素。删除后，为了保持堆的性质，将堆的末尾元素移到堆顶，然后通过一系列比较与交换操作，将它与其子节点比较并移动，直到满足堆的性质为止。
堆化： 将一个无序的数组调整为堆的过程。分为从下往上的“自底向上堆化”和从上往下的“自顶向下堆化”。

建堆

建堆是将一个无序的数组转换成一个堆的过程。

自底向上建堆算法步骤：

从最后一个非叶子节点开始，逐个向上对每个节点进行下滤操作，确保以该节点为根的子树满足堆的性质。复杂度：O(n)。
重复步骤 1，直到根节点，即整个数组被转换成一个堆。

JavaScript 实现自底向上建堆的示例：

function heapifyDown(heap, index, size) {let largest = index;const left = 2 * index + 1;const right = 2 * index + 2;if (left < size && heap[left] > heap[largest]) { // 最大堆的情况，若为最小堆则将判断条件改为 heap[left] < heap[largest]largest = left;}if (right < size && heap[right] > heap[largest]) { // 最大堆的情况，若为最小堆则将判断条件改为 heap[right] < heap[largest]largest = right;}if (largest !== index) {[heap[index], heap[largest]] = [heap[largest], heap[index]]; // 交换节点值heapifyDown(heap, largest, size);}
}function buildHeap(arr) {const n = arr.length;// 从最后一个非叶子节点开始，自底向上进行堆化for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {heapifyDown(arr, i, n);}
}let arr = [4, 10, 3, 5, 1];
buildHeap(arr);
console.log(arr); // 输出结果为 [10, 5, 3, 4, 1]

在上面的示例中，buildHeap 函数将数组 [4, 10, 3, 5, 1] 转换成了一个最大堆。它从最后一个非叶子节点（即节点 10）开始，逐个向上对每个节点进行下滤操作，直到根节点。最终，数组变成了 [10, 5, 3, 4, 1]，满足了最大堆的性质。

自底向上建堆的时间复杂度为 O(n)，其中 n 是数组的长度。这种方法通常比自顶向下建堆更高效，因为它减少了不必要的比较和交换次数。

自顶向下建堆算法步骤：

从数组的第一个元素开始遍历。复杂度：O(nlogn)。
将当前元素插入到堆中。
对插入后的堆进行上滤操作，确保堆的性质被维护。

JavaScript 实现自顶向下建堆的示例：

function heapifyUp(heap, index) {let parentIndex = Math.floor((index - 1) / 2);while (index > 0 && heap[index] > heap[parentIndex]) { // 最大堆的情况，若为最小堆则将判断条件改为 heap[index] < heap[parentIndex][heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]]; // 交换节点值index = parentIndex;parentIndex = Math.floor((index - 1) / 2);}
}function buildHeap(arr) {const n = arr.length;for (let i = 0; i < n; i++) {heapifyUp(arr, i);}
}let arr = [4, 10, 3, 5, 1];
buildHeap(arr);
console.log(arr); // 输出结果为 [10, 5, 3, 4, 1]

在上面的示例中，buildHeap 函数将数组 [4, 10, 3, 5, 1] 转换成了一个最大堆。它遍历数组中的每个元素，并将每个元素插入到堆中，并调用 heapifyUp 函数来确保堆的性质。最终，数组变成了 [10, 5, 3, 4, 1]，满足了最大堆的性质。

自顶向下建堆的时间复杂度为 O(nlogn)，其中 n 是数组的长度。尽管这种方法不如自底向上建堆的效率高，但它仍然是一种有效的方法来构建堆。

堆排序

堆排序是一种利用堆的性质进行排序的算法。基本思路是先建立一个最大堆，然后逐步将堆顶元素与末尾元素交换，并将交换后的堆调整为最大堆，最终得到一个有序数组。以下是 JavaScript 实现：

function heapSort(arr) {// 建立最大堆heapify(arr);let n = arr.length;// 逐步将堆顶元素与末尾元素交换，并调整堆for (let i = n - 1; i > 0; i--) {// 将堆顶元素与末尾元素交换[arr[0], arr[i]] = [arr[i], arr[0]];// 调整堆heapifyDown(arr, 0, i);}
}let arr = [4, 10, 3, 5, 1];
heapSort(arr);
console.log(arr); // 输出结果为 [1, 3, 4, 5, 10]

优先队列

优先队列是一种数据结构，支持插入和取出具有优先级的元素。在堆的基础上，我们可以实现一个最大堆来构建优先队列。JavaScript 中可以通过堆来实现优先队列。

class PriorityQueue {constructor() {this.heap = [];}// 插入元素insert(val) {this.heap.push(val);this.heapifyUp();}// 取出优先级最高的元素extractMax() {if (this.isEmpty()) {return null;}const max = this.heap[0];const last = this.heap.pop();if (this.heap.length > 0) {this.heap[0] = last;this.heapifyDown(0);}return max;}// 自底向上调整堆heapifyUp() {let i = this.heap.length - 1;while (i > 0) {const parent = Math.floor((i - 1) / 2);if (this.heap[parent] < this.heap[i]) {[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];i = parent;} else {break;}}}// 自顶向下调整堆heapifyDown(i) {const n = this.heap.length;let largest = i;const left = 2 * i + 1;const right = 2 * i + 2;if (left < n && this.heap[left] > this.heap[largest]) {largest = left;}if (right < n && this.heap[right] > this.heap[largest]) {largest = right;}if (largest !== i) {[this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];this.heapifyDown(largest);}}// 判断优先队列是否为空isEmpty() {return this.heap.length === 0;}
}// 示例const pq = new PriorityQueue();
pq.insert(10);
pq.insert(5);
pq.insert(20);
console.log(pq.extractMax()); // 输出结果为 20
console.log(pq.extractMax()); // 输出结果为 10
console.log(pq.extractMax()); // 输出结果为 5