【数据结构中的堆】

一、前言

在数据结构中，堆（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 heapq

def 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 算法等。

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