数据结构算法

链表

单链表

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
#include<iostream>
using namespace std;
const int N = 100010;
int head;
int e[N], ne[N], idx;
void init()
{
    head = -1;
    idx = 0;
}
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}
void add(int k,int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}
void dele(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    int n;
    cin >> n;
    init();
    while(n--)
    {
        int x, k;
        char op;
        cin>>op;
        if(op=='H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op=='D')
        {
            cin>>k;
            if(k==0)
                head = ne[head];
            dele(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1;i=ne[i])
    {
        printf("%d ",e[i]);
    }
    printf("\n");
        return 0;
}

这里要搞懂数组模拟链表的原理：
即为插入
注意，在题目中可能会有插入，删除第几个数，因为我们的单链表是从下标0开始的，所以我们这里在导入函数的时候第k个数要导入k-1。
同时，删除第0个数就是删除头节点，相当于直接删除这个单链表，让前面的一切化为乌有。此时就相当于让头节点指向后面那个数的下一个数即为-1，这样就回到了起点，但是注意idx也就是当前第k个数的下标（k-1）是继续保持他原来的样子继续前进，不会重置为0。

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N], r[N], idx;
void init()
{
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}
void add(int x, int k)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
}
void remove(int k)
{
    l[r[k]] = r[k];
    r[l[k]] = l[k];
}

整体思路与单链表相似。

模拟栈&模拟队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int skt[], tt;
int main()
{
    //插入
    {
        int x;
        skt[++tt] = x;
    }
    //删除
    {
        tt--;
    }
    //栈顶
    {
        skt[tt];
    }
    return 0;
}

像是水桶一样，先进后出，后进先出，。
数组模拟栈的概念较为简单，但是不会用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int q[], hh, tt = -1;
int x;
int main()
{
    //插入
    {
        q[++tt] = x;
    }
    //弹出
    {
        hh++;
    }
    //取出
    {
        q[hh];
        q[tt];
    }
    return 0;
}

队列是先进先出，后进后出。
数组模拟的队列中，不仅可以取出队列头，还能取出队列尾。

单调栈和单调队列

单调栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
const int N = 100010;
int n, tt, stk[N];
int main()
{
    cin >> n;
    for (int i = 0; i < n;i++)
    {
        int x;
        cin >> x;
        while(tt&&stk[tt]>=x)
            tt--;
        if(tt)
            cout << stk[tt] << ' ';
        else
            cout << -1 << ' ';
        stk[++tt] = x;
    }
        return 0;
}

题目为，找到这个数左边离他最近的比他小的数，常规思维一定是遍历两次进行暴力算法，但是这样一定会超时，所以我们就想到使用栈的知识来解决。（想得到个蛋）。
就是在左边建立一个栈，每次里面有前面的所有数，如果这个数大于x，那么就把他删了，这样就能建立一个完全的单调函数，那么前面的栈头的数就是这个比x小的离他最近的数。

这个东西泰国巧妙，非一般人类我觉得根本不可能想到。

单调队列

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int tt, hh;
int a[N], q[N];
int n, k;
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n;i++)
    {
        cin >> a[i];
    }
    hh = 0;
    tt = -1;
    for (int i = 0; i < n;i++)
    {
        if(hh<=tt&&q[hh]<i-k+1)
        {
            hh++;
        }
        while(hh<=tt&&a[q[tt]]>=a[i])
        {
            tt--;
        }
        q[++tt] = i;
        if(i>=k-1)
            printf("%d ", a[q[hh]]);
    }
    printf("\n");
    hh = 0;
    tt = -1;
    for (int i = 0; i < n; i++)
    {
        if (hh <= tt && q[tt] < i - k + 1)
        {
            hh++;
        }
        while (hh <= tt && a[q[hh]] <= a[i])
        {
            tt--;
        }
        q[++tt] = i;
        if (i >= k - 1)
            printf("%d ", a[q[hh]]);
    }
    return 0;
}

这种单调队列的题我根本搞不懂，就是说，在这个滑块内，找出最小的值，利用队列，一个一个往里面放值，如果遇到新放进去的值大于小于前一个值的，因为前一个值随着滑块的移动会被先踢出去，所以在他不被踢出去之前，都有后一个数小于他，这样的话，前一个数就是一个无用数，无论区块滑到哪里，他都会被后面一个数取代，所以我们就把她踢掉。

前缀和，双指针

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
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k, a[N];
long long s[N];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n;i++)
    {
        s[i] = s[i - 1] + a[i];
    }
    int x = 1,    ans = 0;
    for (int i = 1; i <= n; i++)
    {
        while(x<=n&&s[x]-s[i-1]<=k)
        {
            ++x;
        }
        ans = max(ans, x - i);
    }
    printf("%d", ans);
    return 0;
}

这种类型的窗口移动就是一个双指针，在一个窗口内，所有数的和小于k，我们就要先定一个指针为i指向第一个元素，然后去寻找最小的前缀和大于k的值，这样那个x-1就是我们要找的最大的x满足前缀和小于k的数，然后因为当i右移的时候，x必定右移，因为x如果左移或者不动的话，那么此时因为少了数，所以肯定不是最大的x满足条件。因此x也是单调右移的，所以我们就可以使用双指针进行遍历。最后求到我们想要的答案。

字符模拟

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
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, c[256];
char s[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n;i++)
    {
        cin >> s[i];
    }
    int tot = 0;
    memset(c, 0 , sizeof(c));
    for (int i = 1; i <= n;i++)
    {
        if(++c[s[i]]==1)
        {
            tot++;
        }
    }
    memset(c, 0,sizeof(c));
    int d = 0;
    int ans = 1 << 30;
    int x = 1;
    for (int i =1; i <= n;i++)
    {
        while(x<=n&&d<tot)
        {
            if(++c[s[x]]==1)
            {
                d++;
            }
            x++;
        }
        if (d == tot)
        {
            ans = min(ans, x - i);
        }
        if(--c[s[i]]==0)
        {
            d--;
        }
    }
    printf("%d", ans);
    return 0;
}

题目本意是有一堆字符，在这个字符里找出最短长度能够包含整个字符串中的所有第一次出现的数。这个题其实也是一个双指针，就是说在i，x这个窗口中，我们去搜寻是否所有字符都已经全部出现，如果不的话就让右边界x++。直到找为止，然后记录下此时的长度，然后再让i右移，减去i所代表的那个字符出现的次数，因为此时无论如何，至少都少了一个字符，所以x一定不能左移，因此就继续依次逻辑往下找。

并查集

合并集合

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
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int find(int x)
{
    if(p[x]!=x)
        p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n;i++)
        p[i] = i;
        while (m--)
        {
            int a, b;
            char op[2];
            scanf("%s%d%d", op, &a, &b);
            if(op[0]=='M')
            {
                p[find(a)] = find(b);
            }
            else
            {
                if(find(a)==find(b))
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
}

这个有点过于巧妙了，在trie的基础上我们规定每一个集合的根节点一致，也就是说每一个集合都有一个根节点，如果要合并两个集合，就让其中一个根节点等于另外一个根节点。如果要查询两个数是否来自同一集合，也只需要看这两个集合的根节点是否一致就行了。

1
2
3
4
5
6
int find(int x)
{
    if(p[x]!=x)
        p[x] = find(p[x]);
    return p[x];
}

精髓就是这个find函数。巧妙地优化了访问根节点的速度。用一个递归就解决了很多问题。
相当于直接指向根节点即可。

连接块中点的数量

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int siz[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        {
            p[i] = i;
            siz[i] = 1;
        }
    while (m--)
    {
        int a, b;
        char op[2];
        scanf("%s", op);
        if (op[0] == 'C')
        {
            cin >> a >> b;
            if(find(a)==find(b))
                continue;
            siz[find(b)] += siz[find(a)];
            p[find(a)] = find(b);
        }
        else if(op[1]=='1')
        {
            cin >> a >> b;
            if (find(a) == find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else 
        {
            cin >> a;
            printf("%d\n", siz[find(a)]);
        }
    }
    return 0;
}

在上一道题的基础之上，只需要加一个操作就是size[N];他表示这个连接块中的点的数量。而size只表示根节点的数，当加入一个数的时候，就把一个数加入另一个根节点的size里面存储，最后看情况取出即可。

食物链

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
#include<iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x)
{
    if(p[x]!=x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n;i++)
        p[i] = i;
        int res=0;
    while(m--)
    {
        int k,x, y;
        cin >> k >> x >> y;
        if(x>n||y>n)
            res++;
        else 
        {
            int px = find(x), py = find(y);
            if(k==1)
            {
                if(px==py&&(d[x]-d[y])%3)
                    res++;
                else if(px!=py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if(px==py&&(d[x]-d[y]-1)%3)
                    res++;
                else if(px!=py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d", res);
    return 0;
}

食物链的本质其实也是并查集。思路比较绕，就是说有三种动物，他们之间形成一个闭环，就是a吃b，b吃c，c吃a。然后现在给定几个条件，要求找出所有谎言。
这里也是一个并查集思路，就是说，加入说有一个根节点，下面是一个集合的。
这时我们找一个数看他与根节点的距离，如果为1就表示能吃根节点，如果为2就表示能吃1，如果为3就表示能吃2，同理2也被根吃，根与3同类。这样的话我们就只需要在一个集合里面去寻找每一个点到根节点的距离即可算出彼此之间的关系。
因为要找距离，所以find函数与之前的find函数有一点不同

1
2
3
4
5
6
7
8
9
10
int find(int x)
{
    if(p[x]!=x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

因为p[x]会发生变化，而我们的d[x]也是靠类似前缀和的思路进行表达的，所以我们就只能先用一个数把变量存起来这样方便我们来求d距离。

代码建议反复观看，因为我觉得这个推理过程不容易想到。。。

kmp字符串

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
#include<iostream>
using namespace std;
const int N = 10010;
const int M = 100010;
int n, m;
char p[N], s[M];
int ne[N];
int main()
{
    cin >> n >> p+1 >> m >> s+1;
    //求next过程
    for (int i = 2, j = 0; i <= n; i++)
    {
        while(j&&p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1])
            j++;
        ne[i] = j;
    }
    //匹配过程
    for (int i = 1,j=0; i <= m;i++)
    {
        while(j&&s[i]!=p[j+1])
        {
            j = ne[j];
        }
        if(s[i]==p[j+1])
            j++;
            if(j==n)
            {
                printf("%d ", i - n);
                j = ne[j];
            }
    }
        return 0;
}

kmp字符串的主要思路就是利用next指针，使得所找到的模板字符串的前缀和后缀相同，这样的话，在我们进行下一组配对的时候我们就可以直接从前缀的后一个，和后缀的后一个直接进行配对

哈希表

模拟散列表

1、拉链法

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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;
int h[N], ne[N], e[N], idx;
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1;i=ne[i])
    {
        if(e[i]==x)
            return true;
    }
    return false;
}
int main()
{
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(*op=='I')
        {
            insert(x);
        }
        else
         {
            if(find(x))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }

    return 0;
}

离散化可以看作是一种很特殊的哈希表，那么他的基本定义也就不难理解，就是将很大的数字存入较小的数组中，以方便存储和查询。因为数据范围一定远远大于哈希表的范围，所以一定存在差错，也就是说会有冲突使得某两个将要被存入哈希表的数存入的值相同，为了避免这种情况的发生，也就诞生了拉链法。
拉链法就是在每一个值相同的位置开一个单链表，将相同的位置上的数存入单链表，这样就能避免出现冲突。

大致就是长这样。这里就是运用单链表的存储和查询方式来进行代码的实现。
这里有一个很神奇的点就是关于模N这个点，因为存在负数的可能，这样%N+N再%N能有效避免负数的存在。

2、开放寻址法

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003,null=0x3f3f3f3f;
int h[N], ne[N], e[N], idx;

int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k]!=null&&h[k]!=x)
    {
        k++;
        if(k==N)
            k = 0;
    }
    
    return k;
}
int main()
{
    int n;
    cin >> n;
    memset(h, 0x3f, sizeof h);
    while (n--)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        int k = find(x);
        if (*op == 'I')
        {
            h[k] = x;
        }
        else
        {
            if (h[k]!=null)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }

    return 0;
}

开放寻址法的思路可以简单理解成蹲坑法，此时我们需要开一个比所需数组大一倍的数组，这样在进行存入操作时可以保证每一个数都能被存进去。在存入数字时，我们常常先进行模运算然后看得到的位置是否已经存在数，如果存在且不是x，那么就继续往下一个走，直至走到没有数的位置。
在查找时也是同理，如果所找到的位置有数且不是x就继续往后找，如果找到null了说明没有数了，说明此时要找的数不存在。

字符串哈希

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
#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int N = 100010,P=131;
int n, m;
char str[N];
ull p[N], h[N];
int get(int l,int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
    scanf("%d%d%s", &n, &m, str + 1);
    p[0] = 1;
    for (int i = 1; i <= n;i++)
    {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + str[i];
    }
    while(m--)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if(get(l1,r1)==get(l2,r2))
            printf("Yes\n");
        else
            printf("No\n");
    }
        return 0;
}

字符串哈希主要利用了前缀和的知识，用一个特殊的值来表示一个特殊的字符串，来判断一个字符串中的任意两个子字符串是否相等，为了使我们找到的特殊值足够特殊，即为不会产生冲突，因此我们需要使用经验值，即为，将字符串当作一个131或者13331进制的一个数，也就是说每一位倒序乘以131或者13331。

然后再让这个数去模2^64 就能得到特殊值来表示特定的字符串。得到了每一个从头开始的字符串的哈希值后，我们再利用前缀和的知识，就可以得到特定区间内的哈希值。
这样就能快速的找出两个字符串是否相同了。

trie字符串

字符串统计

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
#include<iostream>
using namespace std;
const int N = 10010;
int son[N][26], cnt[N], idx;
char str[N];
int n;
void insert(char str[])
{
    int p=0;
    for (int i = 0; str[i];i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}
int query(char str[])
{
    int p=0;
    for (int i = 0; str[i];i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u])
            return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main()
{
    scanf("%d",&n);
    
    while(n--)
    {
        char op[2];
        scanf("%s%s", op, str);
        if(op[0]=='I')
            insert(str);
        else
            printf("%d\n", query(str));
    }
    return 0;
}

从根节点开始，每次的下一个位置存在一个单词，如果该位置已有相同的，那么就在此基础上进行下一个字符的存入，如果没有的话，那么就新开一个数用来存储这个数

1
2
3
if(!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];

在存储的时候有这样一段大代码，这段代码很好的诠释了在对应位置上对应字符的存入，可以多看两眼代码背下来，确实有点牛逼。

最大异或对

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 3000000;
int son[M][2];
int idx;
int a[N];
void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0;i--)
    {
        int &s = son[p][x >> i & 1];
        if(!s)
            {
                s = ++idx;
            }
            p = s;
    }
}
int query(int x)
{
    int p = 0;
    int res = 0;
    for (int i = 30; i >= 0;i--)
    {
        int s = x >> i & 1;
        if(son[p][!s])
        {
            res += 1 << i;
            p = son[p][!s];
        }
        else
        {
            p = son[p][s];
        }
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n;i++)
    {
        
        cin >> a[i];
        insert(a[i]);
    }
    int ans = 0;
    for (int i = 0; i < n;i++)
    {
        ans = max(ans, query(a[i]));
    }
    printf("%d", ans);
    return 0;
}

这道题也是一个trie字符串的题，首先我们要搞懂异或的特性，详细参考位运算那个笔记。
在这里我们需要找出最大异或对，那么我们直接使用2层循环暴力求解肯定会超时，这里第二层循环我们就不能直接使用循环求解，我知道当两个数不一样的时候，异或值为1，所以在一层遍历的基础上我们从最高位开始寻找，尽量找出两个不一样的值，如果存在就继续往后找，如果不存在的话，就只有一样的。
具体思路参考下图：

堆排序

1

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
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int h[N], siz;
void down(int u)
{
    int t = u;
    if (u * 2 <= siz && h[u * 2] < h[t])
        t = 2 * u;
    if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t])
        t = 2 * u + 1;
    if (u != t)
    {
        swap(h[t], h[u]);
        down(t);
    }
}
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &h[i]);
        }
        siz = n;
        for (int i = n / 2; i; i--)
        {
            down(i);
        }
        while (m--)
        {
            printf("%d ", h[1]);
            h[1] = h[siz];
            siz--;
            down(1);
        }

        return 0;

堆排序的本质是一个二叉树，他是用一个一维数组构成的。堆排序与冒泡、归并、快速排一样，是一种全新的排序方式，大体思路是运用二叉树：
至于为什么只对一半的数据进行down操作，这里是一个数学问题，因为二叉树的原因，最底下的一层一定为总数n/2。那么只要让上面的数进行down操作，那么也就相当于对下面的数进行排序了。
在最后的输出环节就只需要进行输出第一个数然后再把他删了，继续输出第一个数，直至达到题目需求输出多少个数。

2模拟堆-数组模拟

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m=0;//输入需要操作的次数
int h[N],ph[N],hp[N],cnt;//h代表heap（堆），ph（point->heap）可以获得第几个插入的元素现在在堆的那个位置
//hp(heap->point)可以获得在堆的第n个元素存的是第几个插入的元素
void heap_swap(int a,int b){//交换在heap中位置分别为a，b的两个元素
    swap(ph[hp[a]],ph[hp[b]]);//根据a和b的位置找到它们分别是第几个插入的元素，然后将其（在h数组中的）下标转换
    swap(hp[a],hp[b]);//将两个位置存的是第几号元素转换
    swap(h[a],h[b]);//最后再转换值(这三个语句位置可以换，但是从上到下逐渐变短的话比较美观)
}
void down(int u){//当前堆的元素下沉
    int t=u;//让t代指u以及其两个儿子（三个点）中的最大值
    if(u*2<=cnt and h[u*2]<h[t])t=u*2;
    if(u*2+1<=cnt and h[u*2+1]<h[t])t=u*2+1;//注意此处为d[t]
    if(u!=t){//最小值不是t，那么下沉，并且继续down操作
        heap_swap(u,t);
        down(t);
    }
}
void up(int u){
    while(u/2 and h[u/2]>h[u]){//第一个u/2是防止当u冲到顶然后陷入死循环
        heap_swap(u/2,u);
        u/=2;
    }
}
int main(){
    cin>>n;
    while(n--){
        string op;//option(选项)的缩写
        int k,x;
        cin>>op;
        if(op=="I"){//insert（插入）的缩写
            cin>>x;
            cnt++,m++;//初始化
            ph[m]=cnt;//m代表是第几个插入的元素(point)->cnt指向的是插入的位置(heap)
            hp[cnt]=m;//原理同上
            h[cnt]=x;//这里忘记写了，WA一次
            up(cnt);
        }else if(op=="PM"){//Print Min 打印最小
            cout<<h[1]<<endl;
        }else if(op=="DM"){
            heap_swap(1,cnt);//将底部一个元素放上来
            cnt--;//所有元素数量减一
            down(1);//将放上来的元素沉下去
        }else if(op=="D"){
            cin>>k;//k存储拿到第几个输入的数字
            k=ph[k];//k从储存第几个输入的数字变换为储存那个数字存放在h的哪个位置
            heap_swap(k,cnt);//将底部一个元素放上来
            cnt--;//所有元素数量减一
            down(k);//其可能大，可能小，都操作一遍准没错
            up(k);
        }else{//剩下来还没有操作的就是C（change）了，不必多谢一个if判断
            cin>>k>>x;
            k=ph[k];//k从储存第几个输入的数字变换为储存那个数字存放在h的哪个位置
            h[k]=x;
            down(k);//这里又忘记写了，WA两次
            up(k);
        }
    }
    return 0;
}

详细情况可以看注解，模拟堆主要是新引入了一个head_swap函数，在此函数中我们能找到并交换堆中的每一个数字的位置下标，以及每一个数字是第几个插进去的。
然后注意up函数的表达与down函数不同。具体的话，就背吧。