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
49
50
#include <bits/stdc++.h>
using namespace std;
// 手写一个堆

// 1.插入一个数
// 2.求集合当中的最小值
// 3.删除最小值
// 4.删除任意一个元素
// 5.修改任意一个元素

const int N = 100010;
int n, m;
int h[N], cnt;

void down(int u)
{
    int 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;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    cnt = n;
    for (int i = n / 2; i; i--)
    {
        down(i);
    }

    while (m--)
    {
        cout << h[1] << endl;
        h[1] = h[cnt--]; // 先等于 cnt为下标的数 ，之后 cnt--
        down(1);
    }

    cout << endl;
    return 0;
}

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
// 手写一个堆

// 1.插入一个数
// 2.求集合当中的最小值
// 3.删除最小值
// 4.删除任意一个元素
// 5.修改任意一个元素

const int N = 100010;
int n, m;
// h数组存的是每个元素
// ph存的是第k个插入的数的对应h数组里的下标
// hp存的是h数组里的某个元素对应ph里面下标
// 例如 a 是第 k 个插入 h数组里的,且在h数组的下标为13，那么h[13] = a, ph[k] = 13，hp[13] = k。
int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    // 知道两个元素在h里的下标a,b，交换两个元素
    swap(ph[hp[a]], ph[hp[b]]); // hp[a] 为该元素是第x个插入的，ph[hp[a]] 为第x元素插入的h数组的下标，
    // 交换对应在 hp数组的值
    swap(hp[a], hp[b]);
    // 交换在数组里面的值
    swap(h[a], h[b]);
}
void down(int u)
{
    int 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;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}
// up操作是将 子节点与根节点进行交换
void up(int u)
{
    while (u / 2 and h[u / 2] > h[u])
    {
        // 如果父节点大于 子节点，那么就一直是子节点向上，因为是小跟堆
        heap_swap(u / 2, u);
        u /= 2;
    }
}
int main()
{
    cin >> n;
    int m = 0;
    while(n--)
    {
        string s1;
        int k,x;
        cin >> s1;
        if(s1 == "I")
        {
            cin >> x;
            cnt++;
            m++;
            ph[m] = cnt;
            hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        } else if(s1 == "PM")
        {
            cout << h[1] << endl;
        } else if(s1 == "DM")
        {
            heap_swap(1,cnt);
            cnt--;
            down(1);
        } else if (s1 == "D")
        {
            cin >> k;
            k = ph[k];
            heap_swap(k,cnt);
            cnt--;
            down(k);
            up(k);
        } else if (s1 == "C")
        {
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            down(k);
            up(k);
        }
    }
   
  
    return 0;
}