Akira的OI(咸鱼)圈

堆

算法
Word count: 367 / Reading time: 2 min
2018/08/16 Share

这里是用一个结构体将堆封装起来，达到类似STL的效果。这是一个小根堆，即保证堆顶的值最小，相对较大的值尽量向下沉。插入一个值即将其放在叶子结点上，不断上浮，直至比其子结点小、比其父节点大。弹出堆顶值即将堆底值与其交换，不断下沉，直至比其子结点小、比其父节点大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 1000001
using namespace std;
struct heap
{
    int data[maxn],len=0;
    inline int get(){return data[1];}
    inline void push(int x)
    {
        data[++len]=x;
        int now =len,Next;
        while(now)
        {
            Next=now>>1;
            if(data[now]>data[Next])
                return;
            swap(data[now],data[Next]);
            now=Next;
        }
    }
    inline void pop()
    {
        data[1]=data[len--];
        int now=1,Next;
        while((now<<1)<=len)
        {
            Next=now<<1;
            if(data[Next]>data[Next+1]&&Next+1<=len)
                Next++;
            if(data[now]<data[Next])
                return;
            swap(data[now],data[Next]);
            now=Next;
        }
    }
};
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
int main()
{    
    heap q;
    int n,x,y;
    n=read();
    while(n--)
    {
        x=read();
        if(x==1)
            y=read(),q.push(y);
        if(x==2)
            printf("%d\n",q.get());
        if(x==3)
            q.pop();
    }
    return 0;
}

原文作者: Akira

原文链接: https://akira-1231.github.io/2018/08/16/堆/

发表日期: 八月 16日 2018, 10:47:02 上午

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 11
2018
题解 算法 杂记