分享程序员开发的那些事...
更新时间：2022-09-27 20:27:57
引入：
最大堆其实非常熟悉，我们用到的地方也很多，最经典的就是排序，它的时间复杂度为o(nlogn),远高于其他排序方式，比较经典的应用比如说一个网关要查看通过它访问的IP/网址列表中，哪些是最热门的IP/网址这种例子，因为访问数量非常多，所以可能有巨大的IP/网址数量，你必须用算法解出其中的最热门的IP/网址然后让网络管理员知道。还有很多类似的例子，特别是TOP-N问题。
分析：
概要：
因为最大堆首先是一个完全二叉树，也就是它的每一行只有排满了才会到下面一行， 所以我们果断的用数组来作为内部存储来节省空间。我们设法吧堆中的元素最大的尽可能放在数组的前面（注意我这里说的是尽可能，而不是一个已经排序了的，这是因为最大堆只要根是所有元素中最大一个并且任意元素都比左右子元素大就可以了，而兄弟之间谁大谁小并没有严格规定）
堆的插入操作：
因为将一个元素插入到一个已经是最大堆中，肯定尽量不希望去破坏其原有堆结构，所以先插到末尾。然后呢，假设这个元素特别大，所以放在末尾显然不符合堆的定义，所以它就必须和其父元素比较，如果比父亲元素大，那么就和父亲元素交换位置，（这就是“上移”操作）一直上移到根部为止。当然了， 你还相应的必须吧堆中当前元素个数变量等更新。
堆的删除操作：
因为对于已经是最大堆来说，最大元素就是堆中首元素，所以直接将其删除就可以了。但是，这样会让原来的最大堆的顶部留一个“孔”，我们必须吧堆中最后一个元素挪到一个合适的位置，从而使得堆的size变小。所以我们需要调节剩余堆使其恢复为一个最大堆，方法是，先把堆的末元素插入到刚才的孔中，然后去比较插入的元素值（孔的新值） ，孔的左子元素，孔的右子元素的大小。如果新插入孔中的元素比左右子元素都大（事实一般不可能），那么说明我们调节好了，因为其他位置都依然保持堆特性我们并没有去破坏。如果新孔元素值不比左或者右子元素大，那么就应该吧新孔元素和子元素较大者交换位置，（这就是"下沉“操作），一直到下沉到堆的底部为止。
**以树状形式打印出堆结构**
这个很多书上都没有介绍，大多数打印都是逐层打印，但是我们思考堆时候在纸上画的图是结构化的，所以用这种扁平数据的表现形式显然不利于我们思考，我们必须仍然保持堆的树形结构。我仔细研究了一个堆，发现堆中每个元素的位置取决于它的当前层数。而且任意一层的元素个数也是确定的。所以我找到了以下规律：
假设最大堆的高度为height,堆中目前总元素个数为currentSize:
则对于第n行，我们可以先打印出Math.pow(2,height-n)个空白char,
然后打印出第n行第一个元素的值，然后打印2*Math.pow(2.height-n)个空白char,依次轮流打印元素值和空白char直到这一行结尾，打印的次数取决于当前的行数，规则如下：
如果是最后一行，那么打印的次数为从currentSize-(Math.pow(2, i-1))
如果不是最后一行，那么打印的次数为Math.pow(2,i-1)
基于以上的分析，我们很快写出了这个堆程序的实现（其实不快，至少我写了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
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
package com.charles.algo.heap;
/** * 这里定义一个最大堆
*
* @author charles.wang
*
*/
public class MaxHeap {
// 最大堆的存储是一个数组,并且为了计算，我们第一个位置不放内容
private int[] data;
// 堆的大小
private int heapSize;
// 当前元素的数量
private int currentSize;
public MaxHeap(int maxSize) {
heapSize = maxSize;
// 创建一个比最大容纳数量多1的数组的作用是启用掉数组的头元素，为了方便运算，因为从1开始的运算更加好算
data = new int[heapSize + 1];
currentSize = 0;
}
/**
* 这里考察堆的插入，因为最大堆内部结构中数组前面元素总是按照最大堆已经构建好的，所以我们总从尾部插入 解决方法是： Step
* 1:先把当前的元素插入到数组的尾部 Step 2:递归的比较当前元素和父亲节点元素， Step
* 3:如果当前的元素大于父亲节点的元素，那么就把当前的元素上移，直到移不动为止
*
* @param value
* @return
*/
public MaxHeap insert(int value) {
// 首先判断堆是否满了，如果满了就无法插入
if (currentSize == heapSize)
return this;
// 如果堆还没有满，那么说明堆中还有位置可以插入，我们先找到最后一个可以插入的位置
// currentPos表示当前要插入的位置的数组下标
int currentPos = currentSize + 1;
// 先插入到当前的位置，因为是从1开始的，所以数组下标运算也要+1
data[currentPos] = value;
// 然后比较当前元素和他的父亲元素
// 当前元素是data[currentPos] ，父亲元素是 data[(currentPos/2],一直遍历到根
int temp;
// 如果currentPos为1，表明是插入的堆中第一个元素，则不用比较
// 否则， 如果插了不止一个元素，则用插入位置的元素和其父元素比较
while (currentPos > 1) {
// 如果当前元素大于父亲元素，那么交换他们位置
if (data[currentPos] > data[currentPos / 2]) {
temp = data[currentPos / 2];
data[currentPos / 2] = data[currentPos];
data[currentPos] = temp;
// 更新当前位置
currentPos = currentPos / 2;
}
// 否则， 在假定已有的堆是最大堆的情况下，说明现在插入的位置是正确的，不用变换
else {
break;
}
}
// 插入完毕之后，吧当前的堆中元素的个数加1
currentSize++;
return this;
}
/**
* 这里考察堆的删除 因为是最大堆，所以肯定删除最大值就是删除堆的根元素，此外，还必须要调整剩余的堆使其仍然保持一个最大堆
* 因为有删除最大元素之后最大元素位置就有了个空位，所以解决方法是： Step 1:吧堆中最后一个元素复制给这个空位 Step
* 2:依次比较这个最后元素值，当前位置的左右子元素的值，从而下调到一个合适的位置 Step 3:从堆数组中移除最后那个元素
*/
public int deleteMax() {
// 如果最大堆已经为空，那么无法删除最大元素
if (currentSize == 0)
return 0;
// 否则堆不为空，那么最大元素总是堆中的第一个元素
int maxValue = data[1];
// 既然删除了最大元素，那么堆中currentSize的尺寸就要-1，为此，我们必须为数组中最后一个元素找到合适的新位置
// 堆中最后一个元素
int lastValue = data[currentSize];
// 先将堆中最后一个元素移动到最大堆的堆首
data[1] = lastValue;
// 把堆内部存储数组的最后一个元素清0
data[currentSize] = 0;
// 并且当前的堆的尺寸要-1
currentSize--;
// 现在开始调整堆结构使其仍然为一个最大堆
int currentPos = 1; // 当前位置设置为根，从根开始比较左右
int leftPos = currentPos * 2;
int leftValue;
int rightValue;
int temp;
// 如果左位置和当前堆的总容量相同，说明只有2个元素了，一个是根元素，一个是根的左元素
if (leftPos == currentSize) {
// 这时候如果根左元素data[2]比根元素data[1]大，那么就交换二者位置
if (data[2] > data[1]) {
temp = data[2];
data[2] = data[1];
data[1] = temp;
}
}
else {
// 保持循环的条件是该节点的左位置小于当前堆中元素个数，那么该节点必定还有右子元素并且位置是左子元素位置+1
while (leftPos < currentSize) {
// 获取当前位置的左子节点的值
leftValue = data[leftPos];
// 获取当期那位置的右子节点的值
rightValue = data[leftPos + 1];
// 如果当前值既大于左子节点又大于右子节点，那么则说明当前值位置是正确的，仍然保持一个二叉树
if (data[currentPos] > leftValue
&& data[currentPos] > rightValue) {
break;
}
// 否则，比较左子节点和右子节点
// 如果左子节点大于右子节点（当然了，同时大于当前节点），那么左子节点和当前节点互换位置
else if (leftValue > rightValue) {
temp = data[currentPos];
data[currentPos] = leftValue;
data[leftPos] = temp;
// 同时更新当前位置是左子节点的位置,并且新的左子节点的位置为左子节点的左子节点
currentPos = leftPos;
leftPos = currentPos * 2;
}
// 如果右子节点大于左子节点(当然了，同时大于当前节点），那么右边子节点和当前节点互换位置
else {
temp = data[currentPos];
data[currentPos] = rightValue;
data[leftPos + 1] = temp;
// 同时更新当前位置是右子节点的位置,并且新的左子节点的位置为右子节点的左子节点
currentPos = leftPos + 1;
leftPos = currentPos * 2;
}
}
}
return maxValue;
}
/**
* 按照树状结构打印出最大堆 这个方法主要思想就是依次打印出每行，其中每行的每个元素它的位置，比如中间空多少，元素元素间隔多少，都和当前行号有关
*/
public void printMaxHeapInTreeShape() {
// 首先计算出树的高度
int height = (int) (Math.log(currentSize) / Math.log(2)) + 1;
// 然后计算出树如果为满二叉树时候最后一行的元素个数
int maxWidth = (int) Math.pow(2, height - 1);
// 打印出每一行
for (int i = 1; i <= height; i++) {
// 打印每一行的算法是：
// 第一行，先打印maxWidth个空白char，然后在打印出第一个元素的值
// 第二行，先打印出maxWidth/2个空白char,然后在打印出第二行第1个元素的值，然后打印maxWidth个空白char，然后打印第二行第2个元素
// 第N行，先打印出maxWidth*Math.pow(2,-(n-1))=Math.pow(2,height-n)个空白char,
// 然后打印出第N行第一个元素的值，然后打印2*Math.pow(2.height-n)个空白char,依次轮流直到这一行结尾
// 所以，先打印Math.pow(2.height-n)个空白char
printSingleBlankCharWithGivenNumber((int) (Math.pow(2, height - i)));
// 在轮流打印出该行元素和元素空白间隔
// 这里例外是最后一行
if (i == height) {
for (int j = (int) (Math.pow(2, i - 1)); j <= currentSize; j++) {
// 打印当前元素
System.out.print(data[j]);
// 打印该行中元素与元素的空白分隔
printSingleBlankCharWithGivenNumber(2 * (int) (Math.pow(2,
height - i)));
}
}
// 否则，这行的元素个数是确定的，所以循环次数为Math.pow(2,i-1) ,其中i为行号
else {
for (int j = (int) (Math.pow(2, i - 1)); j < (int) (Math.pow(2,
i - 1)) + Math.pow(2, i - 1); j++) {
// 打印当前元素
System.out.print(data[j]);
// 打印该行中元素与元素的空白分隔
printSingleBlankCharWithGivenNumber(2 * (int) (Math.pow(2,
height - i)));
}
}
System.out.println();
}
}
/**
* 私有方法，在一行上打印出指定数量的空白字符
*
* @param number
*/
private void printSingleBlankCharWithGivenNumber(int number) {
for (int j = 0; j < number; j++)
System.out.print(" ");
}
} |
实验：
我们先来考察往一个堆中依次乱序加入任意元素的例子，比如我们先申请一个最大容量为15个元素的堆：
|
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
|
//依次插入许多数到堆中,来观察堆的变化 MaxHeap mx = new MaxHeap(15);
System.out.println("空堆已创建:");
System.out.println();
System.out.println("插入4后:");
mx.insert(4);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入6后:");
mx.insert(6);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入5后:");
mx.insert(5);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入12后:");
mx.insert(12);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入3后:");
mx.insert(3);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入13后:");
mx.insert(13);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入9后:");
mx.insert(9);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入15后:");
mx.insert(15);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入14后:");
mx.insert(14);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入8后:");
mx.insert(8);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入10后:");
mx.insert(10);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入2后:");
mx.insert(2);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入1后:");
mx.insert(1);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入7后:");
mx.insert(7);
mx.printMaxHeapInTreeShape();
System.out.println();
System.out.println("插入11后:");
mx.insert(11);
mx.printMaxHeapInTreeShape();
System.out.println();
|
执行结果如下：
|
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
|
空堆已创建:插入4后: 4
插入6后: 6
4
插入5后: 6
4 5
插入12后: 12
6 5
4
插入3后: 12
6 5
4 3
插入13后: 13
6 12
4 3 5
插入9后: 13
6 12
4 3 5 9
插入15后: 15
13 12
6 3 5 9
4
插入14后: 15
14 12
13 3 5 9
4 6
插入8后: 15
14 12
13 8 5 9
4 6 3
插入10后: 15
14 12
13 10 5 9
4 6 3 8
插入2后: 15
14 12
13 10 5 9
4 6 3 8 2
插入1后: 15
14 12
13 10 5 9
4 6 3 8 2 1
插入7后: 15
14 12
13 10 5 9
4 6 3 8 2 1 7
插入11后: 15
14 12
13 10 5 11
4 6 3 8 2 1 7 9
|
下面我们再来演示从最大堆中依次删除最大元素的例子，我们也可以观察删除顺序是否总是从堆中的最大值的，并且删除的顺序是一个排序了的，而且每次删除后剩余堆仍然保持最大堆的形状：
|
1
2
3
4
5
6
7
8
9
10
|
//现在开始演示堆的删除 //因为我们堆中有15个元素，所以我们分15次删除，然后依次来看下每次删除的值是否为堆中最大值以及堆中剩余情况
for(int i=1;i<=15;i++){
System.out.println("第"+i+"次删除:");
System.out.println("被删除的值是:"+mx.deleteMax());
System.out.println("剩余堆为:");
mx.printMaxHeapInTreeShape();
System.out.println();
}
|
结果为：
|
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
|
第1次删除:被删除的值是:15剩余堆为: 14
13 12
9 10 5 11
4 6 3 8 2 1 7
第2次删除:被删除的值是:14剩余堆为: 13
10 12
9 8 5 11
4 6 3 7 2 1
第3次删除:被删除的值是:13剩余堆为: 12
10 11
9 8 5 1
4 6 3 7 2
第4次删除:被删除的值是:12剩余堆为: 11
10 5
9 8 2 1
4 6 3 7
第5次删除:被删除的值是:11剩余堆为: 10
9 5
7 8 2 1
4 6 3
第6次删除:被删除的值是:10剩余堆为: 9
8 5
7 3 2 1
4 6
第7次删除:被删除的值是:9剩余堆为: 8
7 5
6 3 2 1
4
第8次删除:被删除的值是:8剩余堆为: 7
6 5
4 3 2 1
第9次删除:被删除的值是:7剩余堆为: 6
4 5
1 3 2
第10次删除:被删除的值是:6剩余堆为: 5
4 2
1 3
第11次删除:被删除的值是:5剩余堆为: 4
3 2
1
第12次删除:被删除的值是:4剩余堆为: 3
1 2
第13次删除:被删除的值是:3剩余堆为: 2
1
第14次删除:被删除的值是:2剩余堆为: 1
第15次删除:被删除的值是:1剩余堆为: |
结论：
所以，最大堆果然每次插入/删除后都”恢复“为最大堆的形状，并且最大堆的删除顺序已经被排过序。
我们结论也同样适合最小堆。