深入理解堆：原理、实现与应用

创作时间:

作者:

@小白创作中心

深入理解堆：原理、实现与应用

引用

CSDN

https://blog.csdn.net/2302_77582029/article/details/146291304

引言

堆（Heap）是一种特殊的树形数据结构，常用于实现优先队列。它支持高效的插入、删除和查找最值操作，广泛应用于排序、调度和图算法等领域。本文将详细介绍堆的原理、实现方法、优化技巧以及典型应用场景，帮助读者全面掌握这一重要数据结构。

1. 堆的定义与性质

1.1 定义

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

最大堆：每个节点的值大于或等于其子节点的值。
最小堆：每个节点的值小于或等于其子节点的值。

1.2 性质

完全二叉树：堆是一棵完全二叉树，可以用数组高效存储。
堆序性：堆中每个节点的值满足堆的性质（最大堆或最小堆）。

1.3 示例

以下是一个最大堆的示例：

2. 堆的实现

以下是堆的C++实现代码，包括插入、删除和堆化操作。

2.1 堆的结构定义

#include <iostream>
#include <vector>
#include <algorithm>

class MaxHeap {
private:
    std::vector<int> heap;
    // 获取父节点索引
    int parent(int i) {
        return (i - 1) / 2;
    }
    // 获取左子节点索引
    int left(int i) {
        return 2 * i + 1;
    }
    // 获取右子节点索引
    int right(int i) {
        return 2 * i + 2;
    }
    // 上浮操作
    void heapifyUp(int i) {
        while (i > 0 && heap[parent(i)] < heap[i]) {
            std::swap(heap[parent(i)], heap[i]);
            i = parent(i);
        }
    }
    // 下沉操作
    void heapifyDown(int i) {
        int maxIndex = i;
        int l = left(i);
        int r = right(i);
        if (l < heap.size() && heap[l] > heap[maxIndex]) {
            maxIndex = l;
        }
        if (r < heap.size() && heap[r] > heap[maxIndex]) {
            maxIndex = r;
        }
        if (i != maxIndex) {
            std::swap(heap[i], heap[maxIndex]);
            heapifyDown(maxIndex);
        }
    }
public:
    // 插入元素
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }
    // 删除堆顶元素
    int extractMax() {
        if (heap.empty()) {
            throw std::out_of_range("堆为空");
        }
        int max = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
        return max;
    }
    // 获取堆顶元素
    int getMax() {
        if (heap.empty()) {
            throw std::out_of_range("堆为空");
        }
        return heap[0];
    }
    // 打印堆
    void printHeap() {
        for (int i : heap) {
            std::cout << i << " ";
        }
        std::cout << std::endl;
    }
};

2.2 示例代码

int main() {
    MaxHeap heap;
    heap.insert(10);
    heap.insert(7);
    heap.insert(8);
    heap.insert(5);
    heap.insert(6);
    heap.insert(3);
    heap.insert(4);
    std::cout << "堆内容: ";
    heap.printHeap();
    std::cout << "堆顶元素: " << heap.getMax() << std::endl;
    std::cout << "删除堆顶元素: " << heap.extractMax() << std::endl;
    std::cout << "堆内容: ";
    heap.printHeap();
    return 0;
}

2.3 代码解析

插入操作：将新元素插入到堆的末尾，然后通过上浮操作维护堆的性质。
删除操作：将堆顶元素与最后一个元素交换，删除最后一个元素，然后通过下沉操作维护堆的性质。
堆化操作：上浮和下沉操作是维护堆性质的核心。

3. 堆的应用场景

3.1 优先队列

堆常用于实现优先队列，支持高效的插入和删除最值操作。
例如，C++中的std::priority_queue就是基于堆实现的。

3.2 堆排序

堆排序是一种高效的排序算法，时间复杂度为O(n log n)。
示例：

void heapSort(std::vector<int>& arr) {
    MaxHeap heap;
    for (int i : arr) {
        heap.insert(i);
    }
    for (int i = arr.size() - 1; i >= 0; --i) {
        arr[i] = heap.extractMax();
    }
}