【模板】优先队列

优先队列的实现形式之——大根堆

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct data{
    int pq[100010];
    int size=0;
    bool ins[100010];
    void ih()
    {
        pq[0]=0x3f3f3f3f;
        for(int i=1;i<=10010;i++)
        pq[i]=0;
        return ;
    }
    void ip()
    {
        for(int i=1;i<=size;i++)
        {
            printf("%d",pq[i]);
        }
        printf("\n");
        return ;
    }
    void iq(int x)
    {
        if(ins[x]==true) printf("%d is in the queue\n",&x);
        else printf("%d is not in the queue\n",&x);
        return ;
    }
    void top()
    {
        printf("%d ",pq[1]);
        return ;
    }
    void push(int x)
    {
        pq[++size]=x;
        ins[x]=true;
        int n=size;
        while(pq[n/2]<=pq[n])
        {
            swap(pq[n/2],pq[n]);
            n=n/2;
        }
        return ;
    }
    void pop()
    {
        this->top();
        ins[pq[1]]=false;
        swap(pq[1],pq[size]);
        size--;
        int n=1;
        while(n*2+1<=size)
        {
            int now;
            if(pq[n*2]>pq[n*2+1]) now=n*2;
            else now=n*2+1;
            if(pq[n]<pq[now])
            {
                swap(pq[n],pq[now]);
                n=now;
            }
            else break;
        }
        return ;
    }
}pq;

 


主函数自己写233....

上一篇:题解 P1339 【[USACO09OCT]热浪Heat Wave】


下一篇:单源最短路SPFA算法