一维数组模拟堆

1.

 1 /如何手写一个堆？完全二叉树 5个操作
 2 //1. 插入一个数         heap[ ++ size] = x; up(size);
 3 //2. 求集合中的最小值   heap[1]
 4 //3. 删除最小值         heap[1] = heap[size]; size -- ;down(1);
 5 //4. 删除任意一个元素   heap[k] = heap[size]; size -- ;up(k); down(k);
 6 //5. 修改任意一个元素   heap[k] = x; up(k); down(k);
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 int const N = 100010;
12 
13 //h[i] 表示第i个结点存储的值，i从1开始，2*i是左子节点，2*i + 1是右子节点
14 //size 既表示堆里存储的元素个数，又表示最后一个结点的下标
15 int h[N], siz; //堆有两个变量h[N]，size; 怎么这里的size和文件里有冲突，只能改成siz了
16 
17 void down(int u)
18 {
19     int t = u;//t存储三个结点中存在的最小的结点的下标，初始化为当前结点u
20     if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2; // 左子节点存在并且小于当前结点，更新t的下标
21     if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//右子节点存在并且小于当前结点，更新t的下标
22     if (t != u)//如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值
23     {
24         swap(h[t], h[u]);
25         down(t); //交换数值后，t这个结点存储原本u的值，u存储存储t的值（三个数中的最小值）。u不用调整了，但t情况不明，可能需要调整。直到它比左右子节点都小
26     }
27 }
28 
29 int main()
30 {
31     int n, m;
32     cin >> n >> m;
33     for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); 
34     siz = n; //初始化size,表示堆里有n 个元素
35 
36     for (int i = n / 2; i; i --) down(i); //把堆初始化成小根堆，从二叉树的倒数第二行开始，把数字大的下沉
37 
38     while (m -- )
39     {
40         printf("%d ", h[1]);
41         h[1] = h[siz];
42         siz --;
43         down(1);
44     }
45 
46     return 0;
47 }