Py008-01-08堆和堆的向下调整

堆

一种特殊的完全二叉树结构

  • 大根堆：一颗完全二叉树，任意节点都比其孩子节点大
  • 小根堆：一颗完全二叉树，任意节点都比其孩子节点小

一个具体的方式来看堆的问题(如上图的大根堆)

1
2
3
4
第一层 9 好比 省长
第二层 8，7 好比 县长
第三层 6，5，0，1 好比 村长
第四层 2，4，3  好比 村民

堆的向下调整性

假设：节点的左右子树都是堆，但自身不是堆

很明显第一层坐在省长位置的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
于是把 2 撸下来
            ?
    9                  7
  8         5        0  1
6   4     3

让谁上去？待选人肯定是县长级别的   所以是 9 和 7，但是肯定要权限值大的上去

            9
    ？                 7
  8         5        0  1
6   4     3
此时问？ 2能做一个县长吗？ 不能因为它领导不了下面的村长 8和5 而此时需要上位一个县长 8>5  8上位了
            9
    8                 7
  ?         5        0  1
6   4     3
此时问？ 2能做一个村长吗？ 不能因为它领导不了下面的村民 6，4和3 而此时需要上位一个村长 6>4>3  6上位了

            9
    8                 7
  6         5        0  1
?   4     3

最后没法在撸了 ，所以2只能当村民了
        9
    8                 7
  6         5        0  1
2   4     3

堆排序过程演示

原理就是挨个出数

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
res = []
如大根堆的情况：
            9
    8                 7
  6         5        0  1
2   4     3
step001 第一次 先让最大的下台 9下台了 
res=[9]
            ？
    8                 7
  6         5        0  1
2   4     3
---------------------------------
思考假设  让谁上台
如果是8上台
导致8的位置空了
            8
    ?                 7
  6         5        0  1
2   4     3
就必须 6上台
导致6的位置空了
            8
    6                 7
  ?         5        0  1
2   4     3
就必须 4上台
导致4的位置空了
            8
    6                 7
  4        5        0  1
2   ?     3
此时就不知道4的位置有一个空位
这样就很麻烦
这样就很麻烦
这样就很麻烦
---------------------------------
            ？
    8                 7
  6         5        0  1
2   4     3
另一种思路 选一个备胎上去 取树的最后一层的最后的孩子也就是3
            3
    8                 7
  6         5        0  1
2   4     
此时只要通过一次向下调整就能保持堆的层级:如下
            8
    6                 7
  4         5        0  1
2   3   
step002  先让最大的下台 8下台了
取树的最后一层的最后的孩子也就是3
res=[9,8]
            3
    6                 7
  4         5        0  1
2     
通过一次向下调整就能保持堆的层级
res=[9,8]
            7
    6                 3
  4         5        0  1
2   
step003  先让最大的下台 7下台了
取树的最后一层的最后的孩子也就是2
res=[9,8,7]
          2
    6            3
  4   5        0  1
通过一次向下调整就能保持堆的层级
          6
    5            3
  4   2        0  1
step004  先让最大的下台 6下台了
取树的最后一层的最后的孩子也就是1
res = [9,8,7,6]
          1
    5            3
  4   2        0 
通过一次向下调整就能保持堆的层级
           5
    4            3
  1   2        0 
step005  先让最大的下台 5下台了
取树的最后一层的最后的孩子也就是0
res = [9,8,7,6,5]
           0
    4            3
  1   2  
通过一次向下调整就能保持堆的层级       
           4
    2            3
  1   0 
step006  先让最大的下台 4下台了
取树的最后一层的最后的孩子也就是0
res = [9,8,7,6,5,4]
          0
    2            3
  1   
通过一次向下调整就能保持堆的层级 
          3
    2            0
  1 
step007  先让最大的下台 3下台了
取树的最后一层的最后的孩子也就是1
res = [9,8,7,6,5,4,3]
           1
    2            0
通过一次向下调整就能保持堆的层级 
        2
    1        0
step008  先让最大的下台 2下台了
取树的最后一层的最后的孩子也就是0
res = [9,8,7,6,5,4,3,2]
        0
    1        
通过一次向下调整就能保持堆的层级
        1
    0 
step008  先让最大的下台 1下台了
取树的最后一层的最后的孩子也就是0
res = [9,8,7,6,5,4,3,2,1] 
    0
step008  先让最大的下台 0下台了
res = [9,8,7,6,5,4,3,2,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
25
26
27
28
29
30
如
                6
        8               1
    9       3          0  7
   2  4    5

先管理一个村 3
3和5调换
看前一个村 9发现是好的 
                6
        8               1
    9       5          0  7
   2  4    3
村都好了
管理县7
                6
        8               7
    9       5          0  1
   2  4    3
管理前一个县8
                6
        9               7
    8       5          0  1
   2  4    3
县管理好了，管理省6
                9
        8               7
    6       5          0  1
   2  4    3
此时构造堆的过程就结束了

结论就是：每次从最底层构建堆

1
2
3
4
5
6
7
管理村级别的最后一个村
村级别都好了
管理县级别的最后一个县
县级别都好了
管理省级别的最后一个省
县级别都好了
最后就成了一个堆