定义
堆是是一个完全二叉树，其中每个节点的值都大于等于或小于等于其子节点的值。这取决于是最大堆还是最小堆。
-
小根堆：每个根都小于子节点。
-
大根堆：每个根都大于子节点。
以下部分图例说明来源：【从堆的定义到优先队列、堆排序】 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
