数据结构-堆

介绍

堆（Heap）是一种常用的数据结构，它可以在O(1)的时间复杂度内获取到最大值和最小值，同时可以在O(logN)的时间复杂度内完成插入和删除操作。堆通常被用来实现优先队列，堆中的元素按照优先级排序，优先级最高的元素总是位于堆的根节点。

堆可以分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于子节点的值；而在最小堆中，父节点的值总是小于或等于子节点的值。堆通常可以用数组来实现，通过数组的索引可以方便地获取到父节点和子节点。

在堆的操作中，插入元素时，需要将新元素放到数组的末尾，然后调整元素的位置，以保持堆的性质。删除元素时，需要将根节点删除，然后调整剩余元素的位置，以保持堆的性质。获取最大值和最小值时，只需要返回根节点的值即可。

实现举例

最小堆举例

#include <iostream>
#include <vector>
#include <stdexcept>

using namespace std;

class MinHeap {
public:
    MinHeap() {}
    ~MinHeap() {}

    void insert(int val) {
        data.push_back(val);
        int i = data.size() - 1;
        while (i > 0 && data[(i - 1) / 2] > data[i]) {
            swap(data[i], data[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    int extractMin() {
        if (data.empty()) {
            throw invalid_argument("Heap is empty.");
        }
        int result = data[0];
        data[0] = data.back();
        data.pop_back();
        int i = 0;
        while (i * 2 + 1 < data.size()) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int minIndex = left;
            if (right < data.size() && data[right] < data[left]) {
                minIndex = right;
            }
            if (data[i] <= data[minIndex]) {
                break;
            }
            swap(data[i], data[minIndex]);
            i = minIndex;
        }
        return result;
    }

    int getMin() {
        if (data.empty()) {
            throw invalid_argument("Heap is empty.");
        }
        return data[0];
    }

private:
    vector<int> data;
};

最大堆举例

#include <iostream>
#include <vector>
#include <stdexcept>

using namespace std;

class MaxHeap {
public:
    MaxHeap() {}
    ~MaxHeap() {}

    void insert(int val) {
        data.push_back(val);
        int i = data.size() - 1;
        while (i > 0 && data[(i - 1) / 2] < data[i]) {
            swap(data[i], data[(i - 1) / 2]);
            i = (i - 1) / 2;
        }
    }

    int extractMax() {
        if (data.empty()) {
            throw invalid_argument("Heap is empty.");
        }
        int result = data[0];
        data[0] = data.back();
        data.pop_back();
        int i = 0;
        while (i * 2 + 1 < data.size()) {
            int left = i * 2 + 1;
            int right = i * 2 + 2;
            int maxIndex = left;
            if (right < data.size() && data[right] > data[left]) {
                maxIndex = right;
            }
            if (data[i] >= data[maxIndex]) {
                break;
            }
            swap(data[i], data[maxIndex]);
            i = maxIndex;
        }
        return result;
    }

    int getMax() {
        if (data.empty()) {
            throw invalid_argument("Heap is empty.");
        }
        return data[0];
    }

private:
    vector<int> data;
};

总结

堆的应用非常广泛，例如在搜索引擎中，堆可以用来实现关键词的排名；在操作系统中，堆可以用来实现内存分配；在数据挖掘中，堆可以用来实现聚类分析等。