二叉堆

作者： /

一、二叉堆的定义与特性

二叉堆是一种基于完全二叉树的数据结构，分为​​最大堆​​和​​最小堆​​两类：

  • ​​最大堆​​：任意父节点的键值 ≥ 子节点；
  • ​​最小堆​​：任意父节点的键值 ≤ 子节点；
  • ​​完全二叉树特性​​：除最后一层外，其他层节点全满，最后一层节点左对齐。

二、存储结构与索引计算

二叉堆通常用​​数组​​实现，根据根节点下标不同分为两种存储方式：

  1. ​​根节点下标为1​​：
    • 子节点位置：2n（左）、2n+1（右）
    • 父节点位置：n//2（向下取整）
  2. ​​根节点下标为0​​：
    • 子节点位置：2n+1（左）、2n+2（右）
    • 父节点位置：⌊(n-1)/2⌋

​​示例​​：根节点为1的堆数组[_,1,2,3,4,5,6,7]（首元素占位），节点3的子节点为6和7

三、核心操作与算法

1. 插入操作（上浮）

  • ​​步骤​​：插入到数组末尾，逐层与父节点比较并交换，直到满足堆性质；
  • ​​时间复杂度​​： O(log n)

2. 删除堆顶（下沉）

  • ​​步骤​​：
    1. 用末尾元素替换堆顶；
    2. 从根节点开始，与较大（最大堆）/较小（最小堆）子节点交换，直到满足堆性质；
  • ​​时间复杂度​​：O(log n)

3. 建堆算法

  • ​​自顶向下法​​：逐个插入元素，总时间复杂度O(n log n)；
  • ​​自底向上法​​：从最后一个非叶子节点开始调整（Floyd算法），时间复杂度O(n)。

四、性能与应用场景

  1. ​​时间复杂度​​：
    • 查询极值：O(1)；
    • 插入/删除：O(log n)；
    • 合并堆：O(n+k)（数组拼接后重建堆）。
  2. ​​典型应用​​：
    • ​​堆排序​​：通过反复取出堆顶实现排序；
    • ​​优先队列​​：任务调度、Dijkstra最短路径算法；
    • ​​Top K问题​​：维护大小为K的最小堆快速筛选最大元素。

代码实现

#include <bits/stdc++.h>
using namespace std;

class PriorityQueue {
private:
    vector<int> a; // 使用vector来存储堆的元素

    // 上浮操作，用于在插入新元素后恢复堆的性质
    void up() {
        int n = a.size(); // 获取堆的大小
        int i = n - 1; // 新插入元素的位置
        // 当元素不是根节点且比父节点小的时候，执行上浮操作
        while (i > 0 && a[i/2] > a[i]) {
            swap(a[i/2], a[i]); // 交换当前节点和父节点的值
            i /= 2; // 更新当前节点索引为其父节点的索引
        }
    }

    // 下沉操作，用于在删除堆顶元素后恢复堆的性质
    void down() {
        int n = a.size(); // 获取堆的大小
        int i = n - 1; // 最后一个元素的位置
        a[0] = a[i]; // 将最后一个元素移动到堆顶
        a.pop_back(); // 删除最后一个元素
        i--; // 更新堆的大小
        int cur = 0; // 当前节点位置
        int nxt; // 下一个节点位置
        // 当当前节点有子节点时，执行下沉操作
        while (cur <= i) {
            nxt = cur << 1; // 计算左子节点的位置
            // 如果右子节点存在且小于左子节点，选择右子节点
            if (cur << 1 | 1 <= i && a[cur << 1] > a[cur << 1 | 1]) {
                nxt = cur << 1 | 1;
            }
            // 如果当前节点小于其子节点，则不需要继续下沉
            if (nxt > i || a[cur] <= a[nxt]) break;
            swap(a[cur], a[nxt]); // 交换当前节点和最小子节点的值
            cur = nxt; // 更新当前节点索引为最小子节点的索引
        }
    }
public:
    PriorityQueue() {
        a.clear(); // 构造函数，初始化堆
    }

    // 向堆中添加一个元素
    void push(int v) {
        a.push_back(v); // 将新元素添加到数组的末尾
        up(); // 执行上浮操作以恢复堆的性质
    }

    // 获取堆顶元素
    int top() {
        return a[0]; // 堆顶元素即为数组的第一个元素
    }

    // 删除堆顶元素
    void pop() {
        down(); // 执行下沉操作以恢复堆的性质
    }
};

int main() {
    ios::sync_with_stdio(false); // 关闭同步，提高cin和cout的效率
    cin.tie(0); // 解除cin和cout的绑定
    cout.tie(0); // 解除cout的绑定
    auto q = PriorityQueue(); // 创建一个优先队列对象
    int n;
    cin >> n; // 读取操作的数量
    for (int i = 0; i < n; i++) {
        int op;
        cin >> op; // 读取操作类型
        switch (op) {
            case 1:
                int x;
                cin >> x; // 读取要添加的元素
                q.push(x); // 将元素添加到优先队列
                break;
            case 2:
                cout << q.top() << endl; // 打印堆顶元素
                break;
            case 3:
                q.pop(); // 删除堆顶元素
                break;
        }
    }
    return 0;
}
滚动至顶部