在许多应用中，我们需要快速执行一些操作，比如查询和提取数据中的最大值或最小值。举个例子，当我们需要排序学生的考试成绩时，我们可能要频繁地查找和提取最高或最低分。除此之外，这种需求还广泛存在于优先级调度、数据流处理中.

假定我们要解决这样一个问题：有一个集合，每次操作都可能从中添加数据，或取出最大值，应该怎么做？假如使用暴力，仅使用一个数组来维护，我们就需要经常对数据集进行一次遍历（值是 \(O(n)\)）。尽管简单，但如果你需要重复地进行多次这类查询，效率就很低了。这时，二叉堆作为一种高效的数据结构，提供了更好的性能。它能够在 \(O(\log n)\) 的时间复杂度内进行最大值或最小值的查询和删除操作，解决了暴力方法中遍历整个数组的问题.

什么是二叉堆？

二叉堆是一种特殊的二叉树（Binary Tree），对于数来说分为大堆和小堆:

• 大堆 (Max Heap): 根节点的值大于其所有子节点的值，且每个子树的根节点也满足这一性质。
• 小堆 (Min Heap): 根节点的值小于其所有子节点的值，且每个子树的根节点也满足这一性质。

这种数据结构特别适合频繁进行最大值或最小值查询的场景，他们的用途相反，但实现原理是完全一样的，对于上例的题目来说，当然就要使用大根堆。而下图是一个典型的大根堆:

          50
       /      \
     30        40
    /  \      /  \
  10   20   35   25

为什么用数组构建二叉堆？

二叉堆通常用一个数组（Array）来实现，而不是链表。这是因为:

1. 数组实现可以省去链表中用于存储指针的额外空间。
2. 数组实现访问子节点或父节点更加高效，通过索引计算即可完成。这样一个密集完全的二叉树更适合数组法存储。

假如设置根节点是 \(0\) 号，节点在第 \(i\) 位置，那么其左子节点在第 \(2i+1\) 位置，右子节点在 \(2i+2\) 位置，父节点在 \(\lfloor(i-1)/2\rfloor\)。假如设置根节点是 \(1\) 号，节点在第 \(i\) 位置，那么其左子节点在第 \(2i\) 位置，右子节点在 \(2i+1\) 位置，父节点在 \(\lfloor i/2\rfloor\).

建堆时，惯例是直接在原数组上操作，将原数组视为二叉堆，并调整让其符合堆的性质。每次heapify将自身往下都进行比较和调整，保证这一条路径上有序。将每个数据从后往前都进行heapify，就可以使整个数组成为堆。当然，你也可以选择从下向上调整，这是一样的.

#include <vector>
#include <iostream>
using namespace std;

void heapify(vector<int>& heap, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && heap[left] > heap[largest]) {
        largest = left;
    }

    if (right < n && heap[right] > heap[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(heap[i], heap[largest]);
        heapify(heap, n, largest);
    }
}

void buildHeap(vector<int>& heap) {
    int n = heap.size();
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(heap, n, i);
    }
}

处理时间复杂度: \(O(n)\)。构建过程需要对每个非叶子节点进行调整，每次调整的最大操作次数取决于堆的高度。这看似是一个 nlog n 的过程。但实际上，通过 heapify 从最后一个非叶节点开始逐层向上调整，总体时间复杂度为 \(O(n)\)。虽然每次 heapify 操作的时间复杂度是 \(O(\log n)\)，但由于树的高度逐层递减，每层的节点数呈指数下降。因此，整体复杂度是 \(O(n)\)，而不是 \(O(n \log n)\).

堆操作：插入(push)和删除(pop)

1. 建堆 (Build Heap)

通过从底部到顶部逐层对二叉树进行调整，我们可以快速地将无序数组变为二叉堆。上述代码展示了具体的实现方法.

2. 插入操作：Push

插入新元素时，我们需要将该元素添加到数组尾部，然后通过从他开始，不断向上调整来维护堆的性质:

void push(vector<int>& heap, int value) {
    heap.push_back(value);
    int i = heap.size() - 1;

    while (i != 0 && heap[(i - 1) / 2] < heap[i]) {
        swap(heap[i], heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

• 处理时间复杂度: \(O(\log n)\)，因为堆的高度为 \(\log n\)，最多需要向上调整 \(\log n\) 次。

3. 删除操作：Pop

删除堆的根节点时，惯例上，我们保存根节点为需要返回的值后，需要将堆尾元素移动到根节点，移除最后的节点（若不使用 vector 则需要额外的 n 保存数组当前使用的长度），然后通过一次向下调整来恢复堆的性质:

int pop(vector<int>& heap) {
    if (heap.empty()) return -1; // Error case

    int root = heap[0];
    heap[0] = heap.back();
    heap.pop_back();

    heapify(heap, heap.size(), 0);
    return root;
}

当然，你也可以从被删节点开始向上调整，最后删除最后节点.

• 处理时间复杂度: \(O(\log n)\)。调整操作涉及沿树向下的路径。

由于添加和删除总是在数组尾部进行，树总会保持一颗高密度的完全二叉树形态，以保证树高为 \(\log n\) 左右.

---

拓展知识

1. 堆能解决的经典问题

堆在算法设计中有广泛的应用，其功能涵盖了许多经典问题:

• 反悔贪心问题: 在某些贪心算法中，可以通过堆动态调整选择的结果。
• Dijkstra 算法: 优化单源最短路径算法中维护优先级队列的操作。
• Huffman 编码: 使用最小堆构建最优前缀编码树。
• 动态中位数问题: 利用两个堆分别维护较小和较大部分的元素。
• 多路归并 \(k\) 个有序链表: 利用最小堆在每次操作中快速找到最小的头元素。

2. 堆的其他变种

二叉堆只是堆的一种，其效率适中，实现简单，但是不支持合并操作。堆的基本思想被拓展成了许多其他高级变种，每种变种适用于特定的场景:

• 斜堆（Skew Heap）: 实现简单且支持高效合并。
• 左倾堆（Leftist Heap）: 通过维护偏斜度加速合并操作。
• 二项堆（Binomial Heap）: 由一系列二项树组成，适合合并大规模数据。
• 斐波那契堆（Fibonacci Heap）: 用于优化 Dijkstra 等算法中的松弛操作。
• 配对堆（Pairing Heap）: 通过简化操作提升实际效率。
• 优先级搜索队列（Priority Search Queue）: 扩展了堆对键值对的支持。

3. 堆与优先队列的关系

优先队列是指可以进行入队和根据优先级出队的队列，而堆是实现典型优先队列的核心数据结构之一。优先队列的关键操作（插入、取最大/最小值）都可以通过堆实现高效的时间复杂度，许多语言内置了堆操作:

• C++: 使用 std::priority_queue，默认是大根堆，小根堆需自定义比较器。

  #include <queue>
  std::priority_queue<int> maxHeap; // 大根堆
  std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // 小根堆
  

• Python: 使用 heapq 模块，默认是小根堆。

  import heapq
  heap = []
  heapq.heappush(heap, value)  # 插入
  smallest = heapq.heappop(heap)  # 弹出最小值
  

• Java: 使用 PriorityQueue，默认是小根堆。

  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
  

• Go: 使用 container/heap 包。

  import "container/heap"
  

通过掌握这些实现方式，可以在不同的语言中快速构建适合特定场景的优先队列，实现高效的数据处理.

最后此篇关于二叉堆结构和操作详解的文章就讲到这里了,如果你想了解更多关于二叉堆结构和操作详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。