【数据结构中的堆】

---

一、前言

在数据结构中，堆（Heap）是一种特殊的完全二叉树，通常用于实现优先队列（Priority Queue）。堆分为大根堆（Max Heap）和小根堆（Min Heap），分别适用于不同的应用场景，例如堆排序、求Top K问题、Dijkstra最短路径算法等。

本文将介绍堆的概念、基本操作、应用以及C++和Python的代码实现。

---

二、堆的基本概念

1. 堆的定义

堆是一种完全二叉树，并且满足以下性质：

• 大根堆（最大堆）： 父节点的值总是大于等于子节点的值。
• 小根堆（最小堆）： 父节点的值总是小于等于子节点的值。

完全二叉树：如果树的每一层都被完全填满（除了可能的最后一层），并且最后一层的节点靠左对齐，则称其为完全二叉树。

2. 堆的存储方式

堆通常用数组存储，父子关系通过索引计算：

• 父节点索引： parent(i) = (i - 1) / 2
• 左子节点索引： left(i) = 2 * i + 1
• 右子节点索引： right(i) = 2 * i + 2

---

三、堆的基本操作

1. 插入操作（Insert）

插入新元素的步骤：

1. 将元素放入数组的末尾。
2. 进行上浮（Heapify-Up）操作，调整堆结构。

C++ 实现（大根堆）

#include <iostream>
#include <vector>
using namespace std;class MaxHeap {
private:vector<int> heap;void heapifyUp(int index) {while (index > 0) {int parent = (index - 1) / 2;if (heap[parent] >= heap[index]) break;swap(heap[parent], heap[index]);index = parent;}}public:void insert(int value) {heap.push_back(value);heapifyUp(heap.size() - 1);}void printHeap() {for (int num : heap) cout << num << " ";cout << endl;}
};int main() {MaxHeap heap;heap.insert(10);heap.insert(20);heap.insert(5);heap.insert(30);heap.printHeap();return 0;
}

输出示例：

30 20 5 10

---

2. 删除堆顶元素（Extract Max / Min）

删除堆顶元素的步骤：

1. 将堆顶元素与堆的最后一个元素交换，并移除最后一个元素。
2. 进行下沉（Heapify-Down）操作，调整堆结构。

C++ 实现（大根堆）

void heapifyDown(int index) {int size = heap.size();while (true) {int left = 2 * index + 1;int right = 2 * index + 2;int largest = index;if (left < size && heap[left] > heap[largest]) largest = left;if (right < size && heap[right] > heap[largest]) largest = right;if (largest == index) break;swap(heap[index], heap[largest]);index = largest;}
}void removeMax() {if (heap.empty()) return;heap[0] = heap.back();heap.pop_back();heapifyDown(0);
}

---

3. 堆排序（Heap Sort）

堆排序的基本思想：

1. 建堆（Heapify）：将无序数组转换为堆结构。

2. 排序：

   • 交换堆顶元素与最后一个元素，并移除最后一个元素。
   • 重新调整堆结构（Heapify-Down）。
   • 重复此过程，直到所有元素有序。

C++ 实现

void heapSort(vector<int>& arr) {int n = arr.size();// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 交换并调整堆for (int i = n - 1; i > 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

---

五、堆的应用

1. 优先队列

堆可以高效地实现优先队列，使得插入和取出最大（最小）值的时间复杂度为O(log N)。

2. 求 Top K 问题

使用大小为 K 的最小堆，可以在 O(N log K) 的时间内求出前 K 大的元素。

import heapqdef topK(nums, k):return heapq.nlargest(k, nums)  # 取前 K 个最大元素print(topK([3, 1, 5, 12, 2, 11], 3))  # [12, 11, 5]

3. Dijkstra 最短路径算法

在图算法中，堆被用于优化最短路径算法，以高效找到当前最短路径的顶点。

---

六、总结

1. 堆是完全二叉树，常用于实现优先队列。
2. 堆的基本操作：插入（Heapify-Up）、删除（Heapify-Down）、堆排序。
3. 堆的应用广泛，包括 Top K 问题、Dijkstra 算法等。

堆的高效性使其在数据流处理、搜索优化、任务调度等场景下广泛使用，是数据结构中非常重要的一部分。