模拟堆操作：C++实现

发表于   |   分类于 c语言   |   暂无评论

在算法竞赛中，堆常被用来处理需要动态维护最小值或最大值的操作。本文介绍一种基于最小堆的数据结构，支持插入、删除、修改和查询最小值的操作，并且针对每个插入操作进行编号，以便实现按插入顺序删除和修改的功能。

题目描述

我们需要维护一个集合，初始时集合为空，支持如下几种操作：

  • I x，插入一个数 x；
  • PM，输出当前集合中的最小值；
  • DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
  • D k，删除第 k 个插入的数；
  • C k x，修改第 k 个插入的数，将其变为 x。

要求进行 N 次操作，并对于所有 PM 操作，输出当前集合的最小值。

输入格式

  • 第一行包含整数 N；
  • 接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个 PM 操作，输出当前集合的最小值，每个结果占一行。

数据范围

  • 1 ≤ N ≤ 10^5
  • -10^9 ≤ x ≤ 10^9
  • 数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

思路分析

为了在 O(log n) 时间内实现插入、删除和修改操作，同时支持按插入顺序的删除和修改，我们需要用到最小堆，并且引入两个额外的数组来维护插入顺序与堆中元素位置的映射关系。

核心数据结构

  • h[]: 最小堆，存储实际的堆元素；
  • ph[]: 插入元素编号到堆位置的映射，即第 k 个插入的元素当前在堆中的哪个位置；
  • hp[]: 堆中元素的下标对应的插入编号，表示堆中第 i 个位置存储的是第 k 个插入的元素。

这两个数组互为反函数，即 ph[hp[i]] = i，hp[ph[k]] = k。

操作实现

  1. 插入操作 I x：

    • 将新元素插入堆，并更新插入编号和堆中的位置。
    • 调用 up() 函数对堆进行上浮操作。

  2. 输出最小值 PM：

    • 直接输出堆顶元素，即 h[1]。

  3. 删除最小值 DM：

    • 将堆顶元素与堆末尾元素交换，然后删除堆末尾元素。
    • 调用 down() 函数对堆顶进行下沉操作。

  4. 删除第 k 个插入的数 D k：

    • 找到第 k 个插入的元素在堆中的位置，进行删除操作。
    • 调用 down() 和 up() 函数对该位置进行调整。

  5. 修改第 k 个插入的数 C k x：

    • 修改第 k 个插入的元素的值，并进行上下调整，保持堆的性质。

代码实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int h[N], s = 0, hp[N], ph[N]; // ph[]是对应编号元素的下标，hp[]是元素的插入编号，h[]是堆

void heap_swap(int x, int y)
{
    swap(ph[hp[x]], ph[hp[y]]);
    swap(hp[x], hp[y]);
    swap(h[x], h[y]);
}

void down(int x)
{
    int t = x;
    if (x * 2 <= s && h[x * 2] < h[t]) t = x * 2;
    if (x * 2 + 1 <= s && h[x * 2 + 1] < h[t]) t = x * 2 + 1;
    if (x != t)
    {
        heap_swap(x, t);
        down(t);
    }
}

void up(int x)
{
    while (x / 2 && h[x / 2] > h[x])
    {
        heap_swap(x / 2, x);
        x /= 2;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, x, m = 0; // m 表示第几个插入
    string op;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> op;
        if (op == "I")
        {
            cin >> x;
            h[++s] = x;
            hp[s] = ++m;
            ph[m] = s; 
            up(s);
        }
        else if (op == "PM")
        {
            cout << h[1] << '
';
        }
        else if (op == "DM")
        {
            h[1] = h[s--];
            down(1);
        }
        else if (op == "D")
        {
            cin >> k;
            heap_swap(ph[k], s--);
            down(ph[k]), up(ph[k]);
        }
        else if (op == "C")
        {
            cin >> k >> x;
            h[ph[k]] = x;
            down(ph[k]), up(ph[k]);
        }
    }
    return 0;
}

关键点说明

  • heap_swap()：用于交换两个堆元素的位置，同时维护 ph[] 和 hp[] 的映射关系。
  • down()：下沉操作，确保最小堆性质。若子节点比当前节点小，则将当前节点下沉。
  • up()：上浮操作，确保最小堆性质。若父节点比当前节点大，则将当前节点上浮。
  • ph[] 和 hp[] 的作用：这两个数组使得我们可以快速定位并删除或修改任意编号的元素，而无需遍历整个堆。

总结

通过最小堆结合 ph[] 和 hp[] 两个数组，我们能够高效地完成插入、删除、修改和查询最小值的操作。对于每个操作，插入、删除和修改的时间复杂度都是 O(log n)，而查询最小值的操作则为 O(1)。

这类问题广泛应用于需要动态维护有序集合的场景，比如优先队列、任务调度等。
添加新评论