目录

一、堆

1.堆是什么？

2.堆的性质

3.堆的实现

4.基本操作

5.时间复杂度

 二、代码实现

1.最大堆实现

2.最小堆实现

---

一、堆

1.堆是什么？

堆能用树来表示，并且一般树的实现都是通过链表，而二叉堆是一种特殊的堆，它用完全二叉树来表示，却可以利用数组来实现。

平时使用最多的是二叉堆，它可以用完全二叉树俩表示，二叉堆易于存储，并且便于索引。

注意：堆的数据结构像树，但是通过数组实现、

2.堆的性质

• 最大堆：每个节点的值都大于或等于其子节点的值，根节点是最大值。
• 最小堆：每个节点的值都小于或等于其子节点的值，根节点是最小值。

3.堆的实现

1. 通常使用数组实现。对于任意节点在索引 i：
   • 父节点的索引为 (i - 1) / 2
   • 右子节点的索引为 2*i + 2
   • 左子节点的索引为 2*i + 1

4.基本操作

• 插入：将新元素添加到数组末尾，随后进行“上浮”操作，保持堆的性质。
• 删除（通常是删除根节点）：将根节点与最后一个节点交换，移除最后节点，随后进行“下沉”操作，恢复堆的性质。

5.时间复杂度

插入和删除操作的时间复杂度为 O(log n)，而查找最大/最小值的时间复杂度为 O(1)。

 二、代码实现

1.最大堆实现

class MaxHeap {constructor() {this.heap = [];}// 插入元素insert(value) {this.heap.push(value);this.bubbleUp();}// 向上调整bubbleUp() {let index = this.heap.length - 1;while (index > 0) {const parentIndex = Math.floor((index - 1) / 2);if (this.heap[index] <= this.heap[parentIndex]) break;[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];index = parentIndex;}}// 移除最大值extractMax() {if (this.heap.length === 0) return null;if (this.heap.length === 1) return this.heap.pop();const max = this.heap[0];this.heap[0] = this.heap.pop();this.bubbleDown();return max;}// 向下调整bubbleDown() {let index = 0;const length = this.heap.length;while (true) {let leftChildIndex = 2 * index + 1;let rightChildIndex = 2 * index + 2;let largest = index;if (leftChildIndex < length && this.heap[leftChildIndex] > this.heap[largest]) {largest = leftChildIndex;}if (rightChildIndex < length && this.heap[rightChildIndex] > this.heap[largest]) {largest = rightChildIndex;}if (largest === index) break;[this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];index = largest;}}// 查看最大值peek() {return this.heap[0] || null;}// 获取堆的数组表示getHeap() {return this.heap;}
}// 使用示例
const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);
console.log(maxHeap.getHeap()); // [ 20, 10, 5 ]
console.log(maxHeap.extractMax()); // 20
console.log(maxHeap.getHeap()); // [ 10, 5 ]

2.最小堆实现

class MinHeap {constructor() {this.heap = [];}// 插入元素insert(value) {this.heap.push(value);this.bubbleUp();}// 向上调整bubbleUp() {let index = this.heap.length - 1;while (index > 0) {const parentIndex = Math.floor((index - 1) / 2);if (this.heap[index] >= this.heap[parentIndex]) break;[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];index = parentIndex;}}// 移除最小值extractMin() {if (this.heap.length === 0) return null;if (this.heap.length === 1) return this.heap.pop();const min = this.heap[0];this.heap[0] = this.heap.pop();this.bubbleDown();return min;}// 向下调整bubbleDown() {let index = 0;const length = this.heap.length;while (true) {let leftChildIndex = 2 * index + 1;let rightChildIndex = 2 * index + 2;let smallest = index;if (leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallest]) {smallest = leftChildIndex;}if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallest]) {smallest = rightChildIndex;}if (smallest === index) break;[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];index = smallest;}}// 查看最小值peek() {return this.heap[0] || null;}// 获取堆的数组表示getHeap() {return this.heap;}
}// 使用示例
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(20);
minHeap.insert(5);
console.log(minHeap.getHeap()); // [ 5, 10, 20 ]
console.log(minHeap.extractMin()); // 5
console.log(minHeap.getHeap()); // [ 10, 20 ]