最大堆的实现

Created: March 19, 2024 12:12 PM

最大堆是一种二叉树，其中每个父节点的值都大于或等于其子节点的值。这种属性使得树的根节点成为树中的最大值，这对于优先队列和其他需要快速访问最大元素的数据结构非常有用。在C++中，你可以使用STL中的**vector**和一些手动实现的堆操作函数来构建一个最大堆。

下面是如何手动实现最大堆的一个基本示例：

1. 堆的表示

最大堆通常通过数组来表示。对于数组中的任意元素**i**（基于0的索引），其：

• 左子节点在位置**2*i + 1**
• 右子节点在位置**2*i + 2**
• 父节点在位置**(i - 1) / 2**

2. 堆的操作

基本的堆操作包括：

• heapify：用于调整堆，确保满足堆的性质。
• insert：向堆中插入新元素。
• extractMax：移除并返回堆中的最大元素。

示例代码

下面的代码演示了如何手动实现一个最大堆：

cppCopy code
#include <iostream>#include <vector>void heapify(std::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) {
        std::swap(heap[i], heap[largest]);

        // 递归地定义子堆
        heapify(heap, n, largest);
    }
}

void insert(std::vector<int>& heap, int key) {
    heap.push_back(key); // 将新键添加到堆的末尾
    int i = heap.size() - 1; // 获取最后一个元素的索引

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

int extractMax(std::vector<int>& heap) {
    if (heap.size() <= 0)
        return INT_MAX;
    if (heap.size() == 1) {
        int root = heap[0];
        heap.erase(heap.begin());
        return root;
    }

    // 将根（最大值）存储下来，并删除它
    int root = heap[0];
    heap[0] = heap.back();
    heap.pop_back();

    // 调整新堆
    heapify(heap, heap.size(), 0);

    return root;
}

int main() {
    std::vector<int> heap;
    insert(heap, 3);
    insert(heap, 2);
    insert(heap, 15);
    insert(heap, 5);
    insert(heap, 4);
    insert(heap, 45);

    std::cout << "Extracted max: " << extractMax(heap) << std::endl;
    std::cout << "Now max: " << heap[0] << std::endl;

    return 0;
}

这个示例展示了如何通过基本的堆操作来手动管理一个最大堆。这只是一个简单的示例，实际应用中可能需要更多的功能和错误检查。对于大多数应用场景，直接使用C++ STL中的**std::priority_queue**可能更方便，因为它已经提供了一个高效、经过优化的最大堆实现。