什么是堆

讲义概念

优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

GPT概念

堆是一种特殊的数据结构，常用于实现优先队列。在计算机科学中，堆是一个近似完全二叉树的数组对象，这个二叉树除了最后一个层级外，每个层级都是完全填充的，并且所有的节点都尽可能地集中在左侧。堆的主要特点是根节点的键总是最小或最大（即最小堆或最大堆），并且这种性质也适用于每个子树。这意味着，堆不仅保持了树的层次关系，还额外维护了一种排序关系。

堆有两种主要类型：

• 最小堆（Min Heap）：父节点的键总是小于或等于其任何子节点的键。换句话说，最小的元素总是在根处。

• 最大堆（Max Heap）：与最小堆相反，父节点的键总是大于或等于其任何子节点的键。最大的元素总是在根处。

优势（特点）

• 堆的插入和删除操作通常比排序算法（如快速排序、归并排序）更有效率，时间复杂度通常为O(log n)，其中 n 是堆中的元素数量。这使得堆非常适合实现优先级队列，例如在任务调度、路由算法和机器学习等领域都有广泛的应用。

• 堆可以使用数组或链表来实现，不过使用数组实现会更加高效，因为它可以利用数组的索引特性来快速定位节点及其子节点或父节点的位置。

代码实例

这段代码实现了最小堆的所有基本操作，包括插入、删除最小元素和构建堆。你可以通过 insert 方法向堆中添加元素，使用 extractMin 方法获取并移除最小元素。为了初始化堆，可以使用 buildHeap 方法传入一个数组，它会将数组元素重新组织成一个满足堆性质的结构。

class MinHeap {
  constructor() {
    this.heap = [];
  }

  // 插入元素到堆中
  insert(element) {
    this.heap.push(element); // 将元素添加到堆的末尾
    this.bubbleUp(this.heap.length - 1); // 调用bubbleUp方法将新元素调整到正确位置
  }

  // 删除并返回最小元素
  extractMin() {
    if (this.heap.length <= 1) { // 如果堆只有一个元素或为空
      return this.heap.pop(); // 直接弹出该元素
    }
    const min = this.heap[0]; // 假设当前堆顶是最小元素
    this.heap[0] = this.heap.pop(); // 将堆底元素移动到堆顶
    this.sinkDown(0); // 调用sinkDown方法将新的堆顶元素调整到正确位置
    return min; // 返回原来的最小元素
  }

  // 将元素向上移动，确保满足堆的性质
  bubbleUp(index) {
    let parentIndex = Math.floor((index - 1) / 2); // 计算父节点的索引

    while (index > 0 && this.heap[parentIndex] > this.heap[index]) { // 检查父节点是否大于当前节点
      this.swap(parentIndex, index); // 如果是，则交换它们的位置
      index = parentIndex; // 更新索引为父节点索引
      parentIndex = Math.floor((index - 1) / 2); // 更新父节点索引
    }
  }

  // 将元素向下移动，确保满足堆的性质
  sinkDown(index) {
    const leftChildIndex = 2 * index + 1; // 计算左子节点的索引
    const rightChildIndex = 2 * index + 2; // 计算右子节点的索引
    let smallestChildIndex = index; // 假设当前节点是最小的

    if (leftChildIndex < this.heap.length && // 如果左子节点存在
        this.heap[leftChildIndex] < this.heap[smallestChildIndex]) { // 并且比当前节点小
      smallestChildIndex = leftChildIndex; // 更新最小子节点索引
    }

    if (rightChildIndex < this.heap.length && // 同样检查右子节点
        this.heap[rightChildIndex] < this.heap[smallestChildIndex]) { // 并且比当前节点小
      smallestChildIndex = rightChildIndex; // 更新最小子节点索引
    }

    if (smallestChildIndex !== index) { // 如果最小子节点不是当前节点
      this.swap(index, smallestChildIndex); // 交换它们的位置
      this.sinkDown(smallestChildIndex); // 递归地调整新位置
    }
  }

  // 交换数组中的两个元素
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; // 使用解构赋值交换元素
  }

  // 构建堆
  buildHeap(elements) {
    this.heap = elements; // 将传入的数组赋给堆的容器
    for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) { // 遍历从最后一个非叶子节点开始的每个节点
      this.sinkDown(i); // 调用sinkDown方法调整每个节点
    }
  }
}

// 使用示例
const heap = new MinHeap();
heap.insert(10); // 向堆中插入元素
heap.insert(5);
heap.insert(3);
heap.insert(20);
heap.insert(15);

console.log(heap.extractMin()); // 输出: 3
console.log(heap.extractMin()); // 输出: 5

heap.buildHeap([10, 5, 3, 20, 15]); // 用数组构建堆
console.log(heap.extractMin()); // 输出: 3