Heap acwing 839 Simulated reactor

Pile up AcWing 839. Simulation reactor

Original link

AcWing 839. Simulation reactor

Algorithm tags

Pile up

Ideas

Because the title needs to support random modification and deletion , Therefore, each node mapping needs to be stored

Excerpt from the solution
The exchange process

The corresponding code

void heap_swap(int a, int b)
{
	//  As shown in the blue dotted line 
    swap(ph[hp[a]],ph[hp[b]]);
    //  As shown in the green dotted line 
    swap(hp[a], hp[b]);
    //  In the pile a, b At two o 'clock 
    swap(h[a], h[b]);
}

Code

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;
// ph[k] = i To indicate , The first k The inserted number is in h[] Corresponding i How much is the 
// hp{k] = i To indicate , Store... For each heap array k The subscript corresponds to i
int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
	//  As shown in the blue dotted line 
    swap(ph[hp[a]],ph[hp[b]]);
    //  As shown in the green dotted line 
    swap(hp[a], hp[b]);
    //  In the pile a, b At two o 'clock 
    swap(h[a], h[b]);
}

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

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

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            //  Add mapping 
            ph[m] = cnt, hp[cnt] = m;
            //  Insert numbers x
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support