AcWing算法基础课

 1 # 堆
 2 
 3 堆是一个完全二叉树。
 4 
 5 性质：每个节点都满足小于等于它的左右两边的节点。
 6 
 7 存储：1号节点为根节点，x的左儿子：`2x`，x的右儿子：`2x+1`
 8 
 9 
10 
11 操作
12 
13 把节点往下移
14 
15 将根节点大于左儿子和右儿子中的最小值，将根节点与左右儿子中最小的那个交换位置。然后一直交换到不能交换为止。
16 
17 ```cpp
18 void down(){
19     
20 }
21 ```
22 
23 把节点往上移
24 
25 某个数变小后，每次与父节点进行比较就好了，如果比父节点小的话，就要和父节点进行交换
26 
27 ```cpp
28 void up(){
29     
30 }
31 ```
32 
33 如何手写一个堆：
34 
35 1.插入一个数
36 
37 2.求集合当中的最小值
38 
39 3.删除最小值
40 
41 4.删除任意一个元素
42 
43 5.修改任意一个元素
44 
45 
46 
47 1.插入一个数：
48 
49 在当前堆的最后面插入进去，然后进行up操作
50 
51 ```cpp
52 heap[++ size] = x;
53 
54 up(size);
55 ```
56 
57 2.求集合当中的最小值
58 
59 ```cpp
60 heap[1]; 
61 ```
62 
63 3.删除最小值
64 
65 用堆中的最后一个元素覆盖掉第一个元素，size--然后down一下
66 
67 一维数组删掉第一个元素比较难，但是删掉最后一个元素很简单
68 
69 ```cpp
70 heap[1] = heap[size -- ];
71 down(1);
72 ```
73 
74 4.删除任意一个元素
75 
76 ```cpp
77 heap[k] = heap[size]; 
78 size -- ;
79 down(k), up(k);
80 ```
81 
82 5.修改任意一个元素
83 
84 ```cpp
85 heap[k] = x; 
86 down(k), up(k);
87 ```

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 const int N = 100010;
 7 
 8 int n, m;
 9 int h[N], size;
10 
11 void down(int u)
12 {
13     int t = u;
14     if ((u << 1 <= size) && h[u << 1] < h[t]) t = u << 1;
15     if ((u << 1 | 1) <= size && h[u << 1 | 1] < h[t]) t = (u << 1 | 1);
16     
17     if (u != t)
18     {
19         swap(h[u], h[t]);
20         down(t);
21     }
22 }
23 int main()
24 {
25     scanf("%d%d", &n, &m);
26     size = n;
27     for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
28     
29     for (int i = n / 2; i >= 1; i -- ) down(i);
30     
31     while (m -- ) 
32     {
33         printf("%d ", h[1]);
34         h[1] = h[size -- ];
35         down(1);
36     }
37     
38     return 0;
39 }