最小堆建立方法

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 int dis[100];
 5 int t;
 6 void swap(int x, int y)
 7 {
 8     int t;
 9     t = dis[x];
10     dis[x] = dis[y];
11     dis[y] = t;
12 }
13 void check(int i)//检查堆是否符合，不符合就改
14 {
15     int flag = 0, m;//flag为标记当flag不改变时证明不需要继续向上调整
16     while (i * 2 <= t && flag == 0) {//证明不为叶节点
17         if (dis[i] > dis[i * 2])//将左儿子与父节点作比较，用m储存小的节点序号
18             m = i * 2;
19         else
20             m = i;
21         if (i * 2 + 1 <= t) {//查看是否有右儿子
22             if (dis[m] > dis[i * 2 + 1])//将左儿子与父节点中较小的与右儿子作对比，用m储存较小的节点序号
23                 m = i * 2 + 1;
24         }
25         if (m != i) {//当m不等于父节点时证明两个儿子有比父节点小的，将其交换
26             swap(m, i);
27             i = m;
28         }
29         else
30             flag = 1;
31     }
32 }
33 void jiandui()//建立堆,实际上是把所有非叶节点全部检查是否符合最小堆定义（叶节点无儿子，一定满足最小堆定义）
34 {
35     int i;
36     for (i = t / 2;i >= 1;i--) {
37         check(i);
38     }
39 }
40 void out()
41 {
42     for (int i = 1;i <= t;i++)
43         cout << dis[i] << " ";
44 }
45 int main()
46 {
47     
48     cin >> t;
49     for (int i = 1;i <= t;i++) {//先将所有数输入数组，再将其一步步调整为最小堆
50         cin >> dis[i];
51     }
52     jiandui();
53     out();
54 }