堆

1、思路

插入一个数

求集合中的最小值

删除最小值

删除任意一个元素

修改任意一个元素

下标从1开始

堆的结构是一个完全二叉树，只有最下面可能不满。

每个节点小于左右两个儿子的值。所以根节点就是最小值

x的左儿子是2x

x的右儿子是2x+1

down是把一个点往下移，up是把一个节点往上移

插入一个数时间复杂度是logn

heap[++size]=x;
up(size);

求集合中的最小值 O（1）

heap[1];

删除最小值

heap[1]=heap[size];//让第一个点等于最后一个点
size--;
down(1);

删除任意一个元素时间复杂度是longn

删除第k个点
heap[k]=heap[size];
size--;
down(k);            //down和up只会执行一个
up(k);

修改任意一个元素

heap[k]=x;
down(k);
up(k);

2、代码模板

#include<iostream>
#include<algorithm>
using namespace std;
const int N=10010;
int n,m;
int h[N],size;					//h就是堆，size表示当前存了多少元素
void down(int u)
{
	int t=u;					//t是三个点中的最小值 
	if(2*u<=size&&h[2*u]<h[t])	//如果存在左儿子且左儿子小于最小值 
		t=2*u; 					//最小值就是左儿子
	if(2*u+1<=size&&h[2*u+1]<h[t]) //右儿子存在且右儿子小于最小值 
		t=2*u+1;				//最小值就是右儿子
	if(u!=t)					//如果根节点不是最小值 
	{
		swap(h[u],h[t]);		//交换根节点和最小值的位置 
		down(t);				//递归继续 
	} 	 
}
void up(int u)
{
	while(u/2&&h[u/2]>h[u])		//当父节点存在且父节点大于当前的点 
	{
		swap(h[u/2],h[u]);		//与父节点交换位置
		u/=2; 
	}
} 
int main() 
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&h[i]);
	size=n;
	for(int i=n/2;i;i--)		//O(N)的复杂度，n/2的后面都是最后一层，不需要排列 
		down(i); 
	while(m--)
	{
		printf("%d",h[1]);		//输出堆顶 
		h[1]=h[size];			//删除堆顶 
		size--;					//个数减1 
		down(1);				//将堆顶排序 
	}
	return 0;
}

模拟堆：

#include<iostream>
using namespace std;
const int N=1e5+10;
int h[N],n,sum,idx;     //h是堆,记录每个值。sum记录堆中元素总个数，idx记录是第k个插入的
int ph[N];              //ph[]存的值是第k个插入的值在堆(h)里的下标，ph的下标代表第k个插入的数
int hp[N];              //hp[]存的值是堆(h)里面的值是第几个插入点，hp的下标代表值在堆里的下标
void Swap(int a,int b)  //a,b均是在h里的下标，三个顺序不能变，错因为ph的要以hp为索引,hp要以h为索引
{
    swap(ph[hp[a]],ph[hp[b]]);//交换第k个插入对应的下标
    swap(hp[a],hp[b]);  //交换是第几个插入点
    swap(h[a],h[b]);    //交换在堆里的值
}
void down(int u)//u是下标
{
    int t=u;                        //t是三个点中的最小值 
    if(2*u<=sum&&h[2*u]<h[t])       //如果存在左儿子且左儿子小于最小值 
        t=2*u;                      //最小值就是左儿子
    if(2*u+1<=sum&&h[2*u+1]<h[t])   //右儿子存在且右儿子小于最小值
        t=2*u+1;                    //最小值就是右儿子
    if(t!=u)                        //如果父节点不是最小值 
    {
        Swap(t,u);                  //交换根节点和最小值的各种位置 
        down(t);                    //递归继续往下，把堆排好 
    }
}
void up(int u)
{
    while(u/2&&h[u/2]>h[u])         //当父节点存在且父节点大于当前的点 
    {
        Swap(u/2,u);                //与父节点交换位置
        u/=2;
    }
}
int main()
{
    scanf("%d",&n);
    char op[2];
    int k,x;
    while(n--)
    {
        scanf("%s",op);
        if(op[0]=='I')//插入一个值
        {
            scanf("%d",&x);
            h[++sum]=x;//堆里元素总数+1,并且把插入的值先存到堆的最后
            hp[sum]=++idx;//第++idx个插入的。hp记录插入的值在堆中的下标，对应 是第k个插入的
            ph[idx]=sum;//ph存 第idx插入的数对应堆中值的小标
            up(sum);//将新插入的值在堆里排序
        }
        else if(op[0]=='P')//输出集合中最小值，即堆顶元素
            printf("%d\n",h[1]);
        else if(op[0]=='D'&&op[1]=='M')   //删除集合中最小值
        {
            Swap(1,sum);
            sum--;
            down(1);
        }
        else if(op[0]=='D')//删除第k个插入的数
        {
            scanf("%d",&k);
            int u=ph[k];
            Swap(u,sum);
            sum--;
            up(u);
            down(u);
            
        }
        else if(op[0]=='C')//修改第k个数的值，改为x
        {
            scanf("%d %d",&k,&x);
            h[ph[k]]=x;//根据ph存的第k个插入的数在堆中对应的下标
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}