最大堆的JAVA实现

最大堆是一种数据结构,使用完全二叉树来实现,每一个节点都比它的左右孩子节点要大(有点类似于金字塔,数值最大的在塔顶,数值小的在塔底,高度越高,数值越大)

这种结构最适合做什么呢?它,最适合于在一坨数据中找最大值。为甚?大家想想,既然在任何时候塔顶的数都是最大的,这不就意味着我们在任何时候都可以直接抓取最大值了吗,完事了塔顶又是最大值,我们又一次拥有了抓取最大值的机会…如此循环反复,取之不尽用之不竭,子子孙孙无穷无尽也。

堆是怎么实现的呢?

堆的创建

一般来说,堆的物理数据结构是数组(毕竟堆使用了完全二叉树,数组的最经济最划算的选择,根据孩子找父母或是根据父母找孩子都异常简单与方便),数组的第一个元素被放弃使用,因为我们使用child / 2的公式找父母,使用parent * 2parent * 2 + 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
// 堆的创建
private void create(List<Integer> data) {
if (!this.data.isEmpty()) {
this.data.clear();
}

// 舍弃第一个数组元素
this.data.add(0);

// 新元素全部加入数组
this.data.addAll(data);

int parent, child;
// 从最后一个非叶子节点(size / 2)开始调整,直到根
for (int i = (this.data.size() - 1) / 2; i >= 1; i--) {
parent = i;

// 不断地与大于parent的child交换,直到不可交换为止
while (parent <= (this.data.size() - 1) / 2) {
child = parent * 2;

// 右孩子更大
if (child + 1 <= (this.data.size() - 1) && this.data.get(child) < this.data.get(child + 1)) {
child = child + 1;
}

// parent与child交换,并查看是否要继续调整
if (this.data.get(parent) < this.data.get(child)) {
swap(parent, child);
parent = child;
} else {
// parent与child之间已经符合要求,无须交换
break;
}
}

}
}

从上面分析可知,平均复杂度是O(n),最差情况是O(nLogn)

往堆中插入一个数据

由于堆使用了完全二叉树,往堆中插入一个数据时,最好插入到数组尾部(插到其它地方需要移动数组,效率会被拉低),之后将该数据与父母节点比较,并相应做交换,使其逐渐地上浮到相应的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//  往堆中插入一个数据
private void insert(Integer element) {
this.data.add(element);

int parent, child = this.data.size() - 1;

// 从最后一个非叶子节点(size / 2)开始调整,直到根
for (int i = (this.data.size() - 1) / 2; i >= 1; ) {
parent = i;
if (this.data.get(parent) < this.data.get(child)) {
swap(parent, child);
child = parent;
i = i / 2;
}
else {
break;
}
}
}

时间复杂度是O(LogN)

删除堆中数组某个下标的数据

想要删除,直接将最后一个数据覆盖欲删除的数据,之后进行调整即可。

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
// 删除堆中数组某个下标的数据
private void delete(int index) {
this.data.set(index, this.data.get(this.data.size() - 1));
this.data.remove(this.data.size() - 1);

int parent = index, child;

for (; parent >= (this.data.size() - 1) / 2; ) {
child = parent * 2;

// 没有孩子
if (child > this.data.size() - 1) {
return;

// 有左右两个孩子
} else if (child < this.data.size() - 1) {
// 右孩子更大
if (this.data.get(child) < this.data.get(child + 1))
child = child + 1;

// 只有左孩子
} else if (child == this.data.size() - 1) {

}

// 交换parent和child
swap(parent, child);

// 可能要继续下沉
parent = child;
}
}

时间复杂度是O(LogN)