实现一个小顶堆

前言

其实逻辑流程想通了,实现起来就没那么难了。

正文

在写数据结构题时,我们先要搞明白数据结构的定义,以及要写的数据结构有哪些特性,有什么样的行为,有了这些特性、行为的理解,我们才可能写出代码,空中楼阁是造不出来的

可以把数据结构的特性1,2,3,4的列出来再写,另外一开始可以先把次要的元素用简单的东西实现出来(比如我这个小顶堆一开始并没有“节点Node的概念”只是先用一个整形代替了,一开始先关注实现堆的行为,节点是不是对象并不影响堆的行为,可先忽略),实现完主流程然后再回过头来改成更复杂的实现,这样循序渐进,早期把关注点集中在主流程上更容易成功。

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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
package io.since1986.demo;

import java.util.Arrays;
import java.util.StringJoiner;

public class HeapTest {

public static void main(String[] args) {
/*
堆的性质
1. 父节点比左子节点和右子节点都大或比左子节点和右子节点都小
2. 节点和兄弟节点之间的大小无所谓(也就是左右子节点之间大小与位置无关)
3. 每个节点都有编号,根节点编号为1,自根节点向下,从左至右依次顺序编号(也就是编号+1)
4. 每个节点的编号有这样的规律:某个节点N的有左子节点L和右子节点R,L.number = N.number * 2, R.number = N.number * 2 + 1, L.number = R.number + 1


基于堆的上述性质,可以将堆在物理上使用数组存储(编号即是数组索引)
*/

SmallTopHeap smallTopHeap = new SmallTopHeap();
smallTopHeap.add(10);
smallTopHeap.add(7);
smallTopHeap.add(8);
smallTopHeap.add(5);
smallTopHeap.add(9);
smallTopHeap.add(6);
smallTopHeap.add(4);
smallTopHeap.add(3);
smallTopHeap.add(1);
smallTopHeap.add(2);
System.out.println(smallTopHeap);

System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
System.out.println(smallTopHeap.delete());
}

// 小顶堆
static class SmallTopHeap {

// 根节点索引恒定为1
private static final int ROOT_NODE_INDEX = 1;

// 真正的堆的承载数组是需要扩容的,但是我这个只是演示用的堆,写的简单一点,不支持承载数组扩容
private Node[] nodes = new Node[11];

private int largestNodeIndex = ROOT_NODE_INDEX;

SmallTopHeap() {
// 注意数组的索引是从0开始的,但是我为了方便起见,承载数组索引0位置空着不用了,因为概念上堆的索引从要从1开始
nodes[0] = new Node(null);
}

void add(Integer nodeValue) {
if (largestNodeIndex > 10) {
throw new UnsupportedOperationException("这个只是演示用的堆,不支持承载数组扩容");
}

Node currentNode = new Node(nodeValue);

// 插入时总是将要插入的节点放在整个堆的最后
int currentIndex = largestNodeIndex;
nodes[currentIndex] = currentNode;

// 插入节点以后需要更新最大节点的索引+1(加了一个元素因此最大的索引要 + 1)
if (largestNodeIndex < 10) {
largestNodeIndex++;
}

// 如果当前承载数组中还没有存储根节点,那么当前插入的节点就是根节点,插入完成直接返回
if (currentIndex == 1) {
return;
}

// 如果当前承载数组中已经存储了根节点,那么插入完成后就需要进行校验,检查当前堆是否还符合堆的特性
// 也就是从新插入节点的父节点开始一直循环比较大小是关系否合规,直到合规或者已经到根节点为止(根节点是编号最小的节点)

// 找到刚刚插入的节点的父节点 parentElementIndex = currentIndex / 2 这里不用考虑当前是右节点还是左节点,不管是哪个节点,得到父节点编号都是简单的除以2即可,我们可以想一下:
// 假如左子节点索引为 6 那么他的兄弟节点(也就是右节点)索引就是 6 + 1 = 7 父节点索引为 6 / 2 = 3 ,用右节点 7 来推算父节点索引: 7 / 2 = 3,这里 7 除以 2 等于 3 是因为整形除法会丢弃小数点,索引必然都是整形,因此不管是用左子节点还是右子节点来计算父节点的索引,公式都是除以2就可以了
while (true) {
int parentNodeIndex = currentIndex / 2;
Node parentNode = nodes[parentNodeIndex];

// 我们这里是小顶堆(也就是父节点的值小于子节点的值)
if (parentNode.value.compareTo(currentNode.value) < 0) {
// 如果父节点的值小于当前节点的值,是符合小顶堆的特性的,那么循环就可以结束了
break;
}
// 要是父节点的值大于当前节点的值,那么就交换父节点与当前节点
nodes[parentNodeIndex] = currentNode;
nodes[currentIndex] = parentNode;

// 将当前索引设置为父节点索引,并且将当前节点设置为父节点这样就可以进行下次循环了
currentIndex = parentNodeIndex;
currentNode = nodes[currentIndex];

// 循环到了根节点(也就是索引为1的节点)就退出
if (currentIndex == ROOT_NODE_INDEX) {
break;
}
}
}

Integer delete() {
if (largestNodeIndex < 1) {
return -1;
}

// 如果只剩一个了,直接置空并返回
if (largestNodeIndex == 1) {
Node firstNode = nodes[1];
nodes[1] = null;
return firstNode.value;
}

// 堆删除节点一般是删除承载数组第一个元素,然后将承载数组最后一个元素填到第一个元素的位置上,然后将最后一个元素置为null,将最后一个元素放到第一个后会破坏原来堆的性质,需要重新调整让整个承载数组重新符合堆的性质
Node nodeThatBeenDeleted = nodes[1];
Integer result = nodeThatBeenDeleted.value;

Node largestIndexNode = nodes[largestNodeIndex];
nodes[1] = largestIndexNode;
nodes[largestNodeIndex] = null;
largestNodeIndex--;

// 重新调整结构,让承载数组重新符合堆的特性
// 找到左子节点和右子节点,比较一下它们的值大小,将当前节点的值大小与他们两个之中小的那个进行比较,如果值大于就置换(置换后能保证上边的比下边的小,举个例子 假设当前节点值为 10 它的左子节点值为 5,右子节点值为 6,置换后5变为当前节点,比10和6都小,这样是符合小顶堆的性质的),如果小于就返回
int currentIndex = 1;
Node currentNode = nodes[1];

while (true) {
int leftChildNodeIndex = currentIndex * 2;
int rightChildNodeIndex = currentIndex * 2 + 1;

// 特殊流程1:如果左子节点的索引已经大于最大索引了,那直接跳出循环
if (leftChildNodeIndex > largestNodeIndex) {
break;
}

// 特殊流程2:如果左子节点已经是最后一个了,那么直接比较交换并结束循环
if (leftChildNodeIndex == largestNodeIndex) {
Node leftChildNode = nodes[leftChildNodeIndex];
if (leftChildNode.value.compareTo(currentNode.value) > 0) {
break;
}

nodes[currentIndex] = leftChildNode;
nodes[leftChildNodeIndex] = currentNode;
break;
} else {
// 普通流程:左子节点没有到最大索引(此时右子节点有可能是最大索引也有可能不是,倒无所谓,不影响流程,走普通流程就好)
Node leftChildNode = nodes[leftChildNodeIndex];
Node rightChildNode = nodes[rightChildNodeIndex];

// 找到左子节点右子节点中小的那个
Node smallerChild = leftChildNode.value.compareTo(rightChildNode.value) < 0 ? leftChildNode : rightChildNode;
int smallerChildIndex = leftChildNode.value.compareTo(rightChildNode.value) < 0 ? leftChildNodeIndex : rightChildNodeIndex;

// 并于当前节点比较,如果小于就返回(父节点比两个子节点小是符合小顶堆性质的,就不用再置换处理了)
if (smallerChild.value.compareTo(currentNode.value) > 0) {
break;
}

// 当前节点的值大小与他们两个之中小的那个进行比较,如果值大于就置换处理
nodes[currentIndex] = smallerChild;
nodes[smallerChildIndex] = currentNode;

// 并将当前索引置为较小子节点的索引,将当前节点置为较小节点,以便进行下一轮循环
currentIndex = smallerChildIndex;
currentNode = nodes[currentIndex];

// 如果已经到了最大索引,就退出循环
if (currentIndex == largestNodeIndex) {
break;
}
}
}

return result;
}

@Override
public String toString() {
return new StringJoiner(",", "{", "}")
.add("\"nodes\":" + Arrays.toString(nodes))
.add("\"largestNodeIndex\":" + largestNodeIndex)
.toString();
}

static class Node {

private Integer value;

Node(Integer value) {
this.value = value;
}

@Override
public String toString() {
return new StringJoiner(":", "{", "}")
.add("\"value\"")
.add(String.valueOf(value))
.toString();
}
}
}
}

输出:

1
2
3
4
5
6
7
8
9
10
11
{"nodes":[{"value":null}, {"value":1}, {"value":2}, {"value":5}, {"value":4}, {"value":3}, {"value":8}, {"value":6}, {"value":10}, {"value":7}, {"value":9}],"largestNodeIndex":10}
1
2
3
4
5
6
7
8
9
10