8-堆（Heap）

堆是一种特殊的完全二叉树数据结构，满足一定的顺序性质。

所有的节点都大于等于（最大堆）或小于等于（最小堆）它的子节点。由于堆的特殊结构，我们可以用数组表示堆。

堆广泛应用于实现优先队列、堆排序等算法。

基本概念

堆是一棵完全二叉树，满足堆的性质。根据堆的性质，堆分为两种类型：

1.1 最大堆（Max-Heap）

在最大堆中，任何一个节点的值都不小于其子节点的值。也就是说，堆顶元素是整个堆中最大的元素。

• 堆的性质：父节点的值大于或等于子节点的值。
• 堆的形状：完全二叉树，每层节点从左到右依次排列，且最后一层的节点填充到最左边。

1.2 最小堆（Min-Heap）

在最小堆中，任何一个节点的值都不大于其子节点的值。也就是说，堆顶元素是整个堆中最小的元素。

• 堆的性质：父节点的值小于或等于子节点的值。
• 堆的形状：同样是完全二叉树。

表示

    1
   / \
  2   3
 / \  /\
4  5 6

// 数组表示堆结构
const heap = [1, 2, 3, 4, 5, 6]

// 实现一个最小堆类
class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp;
    }
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    getRightIndex(i) {
        return i * 2 + 2;
    }
    shiftUp(index) {
        if (index == 0) { return; }
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
    peek() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
}

const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();

使用场景

• 场景：leetcode刷题

LeetCode题目

● 215  数组中的第K个最大元素
● 347  前 K 个高频元素
● 23  合并K个升序链表

表示

堆通常用一个数组来表示。数组的下标和堆的结构有着密切的关系：

• 父节点：对于一个数组下标为 i 的节点，其父节点下标为 floor((i-1) / 2)。
• 左子节点：对于一个数组下标为 i 的节点，其左子节点下标为 2 * i + 1。
• 右子节点：对于一个数组下标为 i 的节点，其右子节点下标为 2 * i + 2

操作

堆支持几种基本操作，通常包括：

3.1 堆化（Heapify）

堆化是一个将数组调整成堆的过程。通过递归或迭代地调整数组中的元素，使得父节点满足堆的性质。

• 单向堆化：将某个子树调整为堆。
• 全堆化：将整个数组调整为堆。

3.2 插入（Insert）

插入操作用于向堆中添加一个新元素。新元素通常被添加到堆的最后一个位置，然后通过“上浮”（bubble-up）操作将其调整到正确的位置，确保堆的性质不被破坏。

• 步骤：
  1. 将新元素添加到堆的末尾。
  2. 将新元素与其父节点比较，若新元素较大（在最大堆中）或较小（在最小堆中），则交换位置，直到堆的性质得到恢复。

3.3 删除堆顶（Extract Max/Min）

删除堆顶元素是堆的一个重要操作。在最大堆中，堆顶是最大元素，删除后要保持堆的性质。删除堆顶元素的步骤如下：

• 步骤：
  1. 将堆顶元素与堆的最后一个元素交换。
  2. 删除堆的最后一个元素（已交换到堆顶）。
  3. 从堆顶开始，通过“下沉”（sink-down）操作将新的堆顶元素恢复为堆。

3.4 堆排序（Heap Sort）

堆排序是基于堆的排序算法，通过反复提取堆顶元素来排序数组。堆排序的步骤如下：

• 步骤：
  1. 将输入数组构建成最大堆。
  2. 反复删除堆顶元素（最大元素），将其与当前堆的最后一个元素交换。
  3. 调整堆结构，恢复堆的性质。
  4. 重复此过程，直到堆中只剩一个元素。

堆排序的时间复杂度为 O(nlog⁡n)O(n_log_n)，是一个不稳定的排序算法。

3.5 获取堆顶元素（Peek）

获取堆顶元素即访问堆中最大（或最小）元素而不删除它。这个操作时间复杂度为 O(1)O(1)，因为堆顶元素就是堆中最大或最小的元素。

应用

堆具有许多应用，尤其是在处理优先级队列和排序问题时。

4.1 优先队列（Priority Queue）

优先队列是一种抽象数据类型，其中每个元素都关联一个优先级。堆是实现优先队列的一种高效数据结构。

• 最大堆：在优先队列中，具有最高优先级的元素总是位于堆顶。
• 最小堆：在优先队列中，具有最低优先级的元素总是位于堆顶。

4.2 堆排序（Heap Sort）

堆排序是一种基于比较的排序算法，时间复杂度为 O(nlog⁡n)O(n_log_n)，不需要额外的内存空间，因此它是一种原地排序。

4.3 动态中位数计算

可以使用两个堆来动态地计算中位数。通常会使用一个最大堆和一个最小堆来分别存储数据的两部分，从而快速获取中位数。

4.4 图的算法（例如Dijkstra算法）

在图的算法中，堆（通常是最小堆）用于高效地选择当前最短路径的节点。例如，Dijkstra算法通过使用优先队列来优化最短路径的查找。

堆的实现

（Python示例）

在Python中，heapq模块提供了堆的功能，默认实现的是最小堆。

import heapq
# 创建一个空堆
heap = []

# 向堆中添加元素（堆化操作）
heapq.heappush(heap, 20)
heapq.heappush(heap, 10)
heapq.heappush(heap, 30)

# 获取堆顶元素（最小堆，最小元素）
print(heap[0])  # 输出 10

# 删除并返回堆顶元素
min_element = heapq.heappop(heap)
print(min_element)  # 输出 10

# 获取当前堆的堆顶元素
print(heap[0])  # 输出 20

如果需要实现最大堆，可以通过插入负值来模拟：

import heapq
# 创建一个空堆
max_heap = []

# 向堆中添加元素（模拟最大堆）
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -30)

# 获取堆顶元素（最大堆，最大元素）
print(-max_heap[0])  # 输出 30

# 删除并返回堆顶元素
max_element = -heapq.heappop(max_heap)
print(max_element)  # 输出 30

堆（Heap）可以使用 JavaScript 来实现

最大堆的实现

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

  // 获取父节点索引
  parent(index) {
    return Math.floor((index - 1) / 2);
  }

  // 获取左子节点索引
  leftChild(index) {
    return index * 2 + 1;
  }

  // 获取右子节点索引
  rightChild(index) {
    return index * 2 + 2;
  }

  // 判断节点是否是叶子节点
  isLeaf(index) {
    return index >= Math.floor(this.heap.length / 2) && index < this.heap.length;
  }

  // 堆化操作：将堆的某个部分调整为堆
  heapify(index) {
    let largest = index;
    const left = this.leftChild(index);
    const right = this.rightChild(index);

    // 左子节点比父节点大
    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.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      this.heapify(largest);
    }
  }

  // 插入一个元素
  insert(value) {
    this.heap.push(value); // 将元素插入到堆的末尾
    let current = this.heap.length - 1;

    // 向上调整：如果当前元素大于父节点，交换它们
    while (current > 0 && this.heap[this.parent(current)] < this.heap[current]) {
      [this.heap[current], this.heap[this.parent(current)]] = [this.heap[this.parent(current)], this.heap[current]];
      current = this.parent(current);
    }
  }

  // 删除堆顶元素（最大元素）
  extractMax() {
    if (this.heap.length === 0) return null;

    const max = this.heap[0];
    // 将堆顶元素与最后一个元素交换
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop(); // 删除堆顶元素

    // 堆化堆顶元素
    this.heapify(0);

    return max;
  }

  // 获取堆顶元素（最大元素）
  peek() {
    if (this.heap.length === 0) return null;
    return this.heap[0];
  }

  // 获取堆的大小
  size() {
    return this.heap.length;
  }
}

// 示例
const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);
maxHeap.insert(30);
maxHeap.insert(15);

console.log(maxHeap.peek()); // 输出 30
console.log(maxHeap.extractMax()); // 输出 30
console.log(maxHeap.peek()); // 输出 20

要实现最小堆，只需调整条件，使得父节点总是小于或等于其子节点。

最小堆的实现

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

  parent(index) {
    return Math.floor((index - 1) / 2);
  }

  leftChild(index) {
    return index * 2 + 1;
  }

  rightChild(index) {
    return index * 2 + 2;
  }

  isLeaf(index) {
    return index >= Math.floor(this.heap.length / 2) && index < this.heap.length;
  }

  heapify(index) {
    let smallest = index;
    const left = this.leftChild(index);
    const right = this.rightChild(index);

    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }

    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }

    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.heapify(smallest);
    }
  }

  insert(value) {
    this.heap.push(value);
    let current = this.heap.length - 1;

    while (current > 0 && this.heap[this.parent(current)] > this.heap[current]) {
      [this.heap[current], this.heap[this.parent(current)]] = [this.heap[this.parent(current)], this.heap[current]];
      current = this.parent(current);
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;

    const min = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();

    this.heapify(0);

    return min;
  }

  peek() {
    if (this.heap.length === 0) return null;
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }
}

// 示例
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(20);
minHeap.insert(5);
minHeap.insert(30);
minHeap.insert(15);

console.log(minHeap.peek()); // 输出 5
console.log(minHeap.extractMin()); // 输出 5
console.log(minHeap.peek()); // 输出 10