Category:洛谷题库
Article From:https://www.cnblogs.com/Xray-luogu/p/9123212.html

Title address:

$Luogu$:https://www.luogu.org/problemnew/show/P3378

So when we see the topic, we should write this question.

We need three operations.

1、Insert a number into a small root heap(Small root team (Young Pioneers)

2、The minimum value of the output of the small root heap.

3、Delete the minimum value of the small root heap.

Because we know that the minimum value of a small heap is its root, so this question is very simple.

You have nothing to do with $N< =10^6$, it doesn’t matter.

The first and third operations we need to write two functions to solve. The second operations can be directly output.

The first function: the insert function.

void insert(int x)
{
    h[++l]=x;
    up(l);
}

The second function: delete the function.

void _delete(int x)
{
    h[x]=h[l--];
    up(x);
    down(x);
}

The function of floating operation $up$and sinking operation $down$is also attached.

void up(int x)
{
    while(x>1&&h[x]<h[x>>1])
    {
        swap(h[x], h[x>>1]);
        x>>=1;
    }
}
void down(int x)
{
    int y=x<<1;
    while(y<=l)
    {
        if(y+1<=l&&h[y+1]<h[y]) y++;
        if(h[y]<h[x])
        {
            swap(h[x], h[y]);
            x=y, y=x<<1;
        }
        else break;
    }
}

The code is as follows:

$code$

#include<bits/stdc++.h>
using namespace std;
const int maxN=1000000+1;
int h[maxN], n, l;
void read(int &), insert(int), up(int), down(int), _delete(int);
int main()
{
	read(n);
	for(int i=1; i<=n; i++)
	{
		int x;
		read(x);
		if(x==1)
		{
			int y;
			read(y);
			insert(y); 
		}
		if(x==2) printf("%d\n", h[1]);
		if(x==3) _delete(1);
		
	}
	return 0;
}
void read(int &x)
{
	x=0;
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
}
void up(int x)
{
	while(x>1&&h[x]<h[x>>1])
	{
		swap(h[x], h[x>>1]);
		x>>=1;
	}
}
void down(int x)
{
	int y=x<<1;
	while(y<=l)
	{
		if(y+1<=l&&h[y+1]<h[y]) y++;
		if(h[y]<h[x])
		{
			swap(h[x], h[y]);
			x=y, y=x<<1;
		}
		else break;
	}
}
void insert(int x)
{
	h[++l]=x;
	up(l);
}
void _delete(int x)
{
	h[x]=h[l--];
	up(x);
	down(x);
}

  

Link of this Article: P3378 [template] heap

Leave a Reply

Your email address will not be published. Required fields are marked *