封面画师:ツチヤ     封面ID:78809165

本文参考视频:小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法(第一季)

源码仓库:mofan212/data-structure-and-algorithm (github.com)

辅助学习网址:数据结构和算法动态可视化

0. 需求分析

现需要设计一种数据结构,用来存放整数,要求提供三个接口:

  • 添加元素
  • 获取最大值
  • 删除最大值

可以用很多方式来实现这个需求,比如动态数组、双向链表、BBST 等,它们的时间复杂度对比如下:

获取最大值 删除最大值 添加元素 吐槽
动态数组 \ 双向链表 O(n) O(n) O(1)
有序 动态数组 \ 双向链表 O(1) O(1) O(n) 全排序有点浪费
BBST O(logn) O(logn) O(logn) 杀鸡焉用牛刀?

通过上面的对比可知 BBST 的综合效率更高,难道就采用红黑树或 AVL 树来实现?

你是憨批

BBST 内部逻辑多复杂心里没点数?BBST 的功能也很强大,能做很多事,然后就拿来做这三个需求?那不是杀鸡用了牛刀?

那有没有更优的数据结构来实现呢?

那肯定是有的! 可以使用 !😎

堆的时间复杂度如下:

获取最大值 删除最大值 添加元素
O(1) O(logn) O(logn)

至此还可以引入一个问题: Top K 问题。💃

Top K 问题

所谓 Top K 问题,就是从海量数据中找出前 K 个数据。

比如: 从 100 万个整数中找出最大的 100 个整数。

Top K 问题的解法之一: 可以用数据结构 “堆” 来解决。💪

1. 堆的含义

堆(Heap)也是一种树状的数据结构(不要跟内存模型中的“堆空间”混淆),常见的堆实现有:

  • 二叉堆(Binary Heap,完全二叉堆)
  • 多叉堆(D-Heap,D-ary Heap)
  • 索引堆(Index Heap)
  • 二项堆(Binomial Heap)
  • 斐波那契堆(Fibonacci Heap)
  • 左倾堆(Leftist Heap,左式堆)
  • 斜堆(Skew Heap)

本文主要介绍二叉堆!

堆的性质

堆有一个重要的性质:任意节点的值总是 大于等于 (或小于等于)其 子节点 的值。

如果任意节点的值总是 大于等于 其子节点的值,称为:最大堆、大根堆、大顶堆,但这并不是说上一层的节点值一定大于等于下一层的节点值。如:

最大堆_二叉堆

如果任意节点的值总是 小于等于 其子节点的值,称为:最小堆、小根堆、小顶堆,同样也不是说上一层的节点值就一定小于等于下一层的节点值。如:

最小堆_二叉堆

通过图示可以发现:对于最大堆,整个堆的最大值就是在最上面的根节点;对于最小堆,整个堆的最小值就是在最上面的根节点。

由此可见,堆中的元素必须具备可比较性(跟二叉搜索树一样)。

接口设计

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @author 默烦
* @date 2020/8/4
*/
public interface Heap<E> {
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void clear(); // 清空
void add(E element); // 添加元素
E get(); // 获取堆顶元素
E remove(); // 删除堆顶元素
E replace(E element); // 删除堆顶元素的同时插入一个新元素
}

2. 二叉堆

2.1 基本含义

二叉堆逻辑结构 就是一棵完全二叉树,所以也叫 完全二叉堆

二叉堆示意图:

二叉堆

鉴于完全二叉树的一些特性,二叉堆的底层( 即物理结构)一般用数组实现即可。

那为什么不用二叉树或者链表作为物理结构呢?

  • 如果使用二叉树作为物理结构,在编写节点对象,还要存储 left 、right 指针等各种东西,内存结构将变得复杂。
  • 因为是完全二叉堆,其元素的摆放位置是从上到下、从左到右的,在这样的规则下选用数组作为物理结构是最好的。

针对上图给出的二叉堆示意图,其物理结构可以表示为:

二叉堆物理结构

索引 i 的规律(n 是元素数量)

如果 i = 0 ,它是 节点。

如果 i > 0 ,它的 节点索引为 floor((i - 1) / 2)

如果 2i + 1 <= n - 1 ,它的 子节点索引为 2i + 1

如果 2i + 1 > n - 1 ,它 无左 子节点。

如果 2i + 2 <= n - 1 ,它的 子节点索引为 2i + 2

如果 2i + 2 > n - 1 ,它 无右 子节点。

2.2 基本接口实现

接下来基于二叉堆,编写一个最大堆。

创建实现 Heap 接口二叉堆 BinaryHeap 类。

由于二叉堆的底层是由数组实现的,因此需要成员变量 size 来表示二叉堆的长度,还需规定数组的默认容量,为编写扩容代码做准备。

二叉堆的逻辑结构是完全二叉搜索树,因此要求节点有可比较性。

针对以上说明,可以实现一些简单的方法:

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
/**
* 二叉堆(最大堆)
* @author 默烦
* @date 2020/8/4
*/
public class BinaryHeap<E> implements Heap<E> {
private E[] elements;
private int size;
private Comparator<E> comparator;
private static final int DEFAULT_CAPACITY = 10;

public BinaryHeap(Comparator<E> comparator) {
this.comparator = comparator;
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}

public BinaryHeap(){
this(null);
}

@Override
public int size() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}

@Override
public void add(E element) { }

@Override
public E get() { // 获取堆顶元素
// 判断堆是否为空
emptyCheck();
return elements[0];
}

@Override
public E remove() {
return null;
}

@Override
public E replace(E element) {
return null;
}

private int compare(E e1, E e2){
return comparator != null ? comparator.compare(e1, e2)
: ((Comparable<E>) e1).compareTo(e2);
}

// 检查二叉堆 size 是否为 0
private void emptyCheck(){
if (size == 0){
throw new IndexOutOfBoundsException("Heap is empty!");
}
}
}

2.3 添加元素

再次声明:具体实现是基于二叉堆的最大堆。

前文说到:二叉堆的物理结构是数组,那应该怎么添加元素呢?

直接这样?🙋

1
2
3
4
@Override
public void add(E element) {
elements[size++] = element;
}

那肯定不是啊!咋可能这么简单。😏

添加思路

首先,要求添加的元素需要有可比较性,因此添加元素时必须判断是否为 null,对此可以写一个检测空值的方法然后在添加方法 add() 中调用:

1
2
3
4
5
private void elementNotNullCheck(E element){
if (element == null){
throw new IllegalArgumentException("element must not be null!");
}
}

添加元素时还可能出现数组容量不够的情况,此时需要对数组进行扩容。这里可以使用在动态数组中编写的扩容方法 ensureCapacity(),这也要在 add() 方法中调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 保证要有capacity的容量(不考虑线程安全)
private void ensureCapacity(int capacity){
// 当前 elements.length 为 10,因为默认容量为 10
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为新容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}

还有最最重要的一点: 如果直接在数组末尾添加元素,可能会破坏二叉堆的结构,因此添加元素后需要对二叉堆的结构进行修复。

假设在一个二叉堆中添加元素 80,那么修复步骤如下:

二叉堆添加示意图

对上图的修复步骤进行总结(图中的 80 简称为 node):

循环执行以下操作:

  • 如果 node > node 的父节点,那么当前节点与父节点交换位置;
  • 如果 node <= node 的父节点,或者 node 没有父节点,退出循环。

这个过程被称为上滤(Sift Up)。添加元素的时间复杂度为 O(logn)

添加元素的实现

编写一个方法,这个方法可以让索引 index 位置的元素进行上滤:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 让索引为 index 的元素进行上滤
*
* @param index 数组索引
*/
private void siftUp(int index) {
E e = elements[index];
while (index > 0) { // 索引位置节点有父节点时
int pIndex = (index - 1) >> 1; // 获取父节点索引
E p = elements[pIndex];
if (compare(e, p) <= 0) return;
// 交换 index、pIndex 位置的内容
E tmp = elements[index];
elements[index] = elements[pIndex];
elements[pIndex] = tmp;
// 重新赋值 index
index = pIndex;
}
}

最后,在添加方法 add() 中对三个私有方法进行汇总:

1
2
3
4
5
6
7
@Override
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}

2.4 代码优化

上滤优化

上滤 siftUp() 的具体实现中进行了位置交换,而位置交换的代码需要三行,这里还可以进行优化:将新添加节点备份,确定最终位置后才摆放上去

好像有点抽象?💫具体而言:

  • 先将插入的元素备份一手;
  • 然后用插入元素与其父元素进行比较,如果大于父节点,就用父节点的数据添加到插入元素的位置;
  • 使用同样的方法,插入元素一直向上比较循环,直到没有父节点,或小于等于父节点;
  • 最后用备份的插入节点覆盖父节点。

具体流程图如下:

二叉堆上滤优化流程

代码修改如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 让索引为 index 的元素进行上滤
*
* @param index 数组索引
*/
private void siftUp(int index) {
E e = elements[index];
while (index > 0) { // 索引位置节点有父节点时
int pIndex = (index - 1) >> 1; // 获取父节点索引
E p = elements[pIndex];
if (compare(e, p) <= 0) break;

// 将父元素存储在 index 位置
elements[index] = elements[pIndex];
// 重新赋值 index
index = pIndex;
}
elements[index] = e;
}

对比未优化的代码可以发现,在 while 循环中减少了三条语句。

仅从交换位置的代码角度看:大概由 3 * O(logn) 优化到 1 * O(logn) + 1

代码抽取

介绍堆的时候列举过很多的堆实现,比如:多叉堆、索引堆、斐波那契堆等等。有这么多的堆实现,它们中肯定有些代码是可以复用的,因此可以将这些公共代码抽取出来。

创建一个抽象类 AbstractHeap,实现Heap接口,用于抽取堆中的公共代码。

堆中的元素肯定是有可比较性的,同时成员变量 size 也肯定是每个堆都有的。基于 size 成员变量,size() 方法和 isEmpty() 方法也应该都是可以共用的,比较方法 compare() 也不例外。

PS: 注意抽象类中方法、成员变量的访问修饰符!

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
/**
* @author 默烦
* @date 2020/8/4
*/
public abstract class AbstractHeap<E> implements Heap<E> {
protected int size;
protected Comparator<E> comparator;

public AbstractHeap(Comparator<E> comparator) {
this.comparator = comparator;
}

public AbstractHeap() {
this(null);
}

@Override
public int size() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

protected int compare(E e1, E e2) {
return comparator != null ? comparator.compare(e1, e2)
: ((Comparable<E>) e1).compareTo(e2);
}
}

然后可以用 BinaryHeap 继承抽象类 AbstractHeap,取消实现 Heap,并将 BinaryHeap 类中的公共方法、公共成员变量删除:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class BinaryHeap<E> extends AbstractHeap<E> {
// 删除了两个存在于父类的成员变量
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;

// 这个构造方法也要修改
public BinaryHeap(Comparator<E> comparator) {
super(comparator);
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}

// 删除方法 size()、isEmpty() 和 compare()

// 省略其他代码
...
}

2.5 删除元素

删除元素的抽象方法是: E remove();,方法并没有接收任何参数,这意味着不能在这里的堆中删除指定的元素,其含义指的是 删除堆顶的元素

那应该怎么删除? 🙋

直接删除物理结构中数组中的元素,然后让后面的元素向前移,就和动态数组一样?

那肯定不是,如果这样的话,删除元素的时间复杂度就高达 O(n) 了。😥

删除思路

假设现有一个二叉堆如下图所示,需要删除其堆顶元素 80 ,具体删除步骤如下:

二叉堆删除示意图

对上述删除步骤进行总结:

  • 用最后一个节点覆盖根节点
  • 删除最后一个节点
  • 循环执行以下操作(图中的 43 简称为 node):
    • 如果 node < node 的子节点,与最大的子节点交换位置
    • 如果 node >= node 的子节点,或者 node 没有子节点,就退出循环

在添加元素中存在上滤,既然有上滤,那么就有下滤,这里的过程就叫做下滤(Sift Down),时间复杂度为:O(logn),同样在下滤中交换位置的操作也可以像上滤那样进行优化。

删除实现

首先得搞清楚循环的条件,其实很简单:循环到第一个叶子节点就停止循环。

因此得找到第一个叶子节点的索引,二叉堆的逻辑结构是一棵完全二叉树,根据完全二叉树的规律可知: 第一个叶子节点的索引等于非叶子节点的数量

在完全二叉树中,非叶子节点的数量为 floor(n / 2),其中 n 为节点的总数量。这样,循环条件就确定了!👏

然后就是找到节点的左右节点,并与其中最大的节点进行比较替换。这里有一点可以注意一下,在完全二叉树中,一个节点要么只有左子节点,要么左右子节点都有,不可能出现只有右子节点的情况,因此可以设置默认的比较节点为左子节点。

编写一个方法,这个方法可以让索引 index 位置的元素进行下滤:

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
/**
* 让索引为 index 的元素进行下滤
*
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// 第一个叶子节点的索引 = 非叶子节点的数量
while (index < half){ // 必须保证index位置是非叶子节点
/*
* index 位置的节点的子节点有两种情况
* 1. 只有左子节点
* 2. 同时有左子节点、右子节点
*/
// 默认为左子节点的索引
int childIndex = (index << 1) + 1;
E child = elements[childIndex];

// 右子节点索引
int rightIndex = childIndex + 1;
// 选出最大的子节点
if (rightIndex < size
&& compare(elements[rightIndex],child) > 0){
// childIndex = rightIndex;
child = elements[childIndex = rightIndex];
}

if (compare(element,child) >= 0) break;
// 将子节点存放到index位置
elements[index] = child;
// 重新设置index
index = childIndex;
}
elements[index] = element;
}

最后,完善一下删除堆顶方法 remove()

1
2
3
4
5
6
7
8
9
10
11
12
@Override
public E remove() { // 删除堆顶元素
emptyCheck();

int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;

siftDown(0);
return root;
}

2.6 replace 方法

replace 方法的完整签名是 E replace(E element);,表示删除堆顶元素的同时插入一个新元素。

既然如此,不难想到这么实现 replace() 方法:

1
2
3
4
5
6
@Override
public E replace(E element) {
E root = remove();
add(element);
return root;
}

这么做…

确实可以。😂

但有点欠妥,因为删除、添加都是 O(logn) 级别的,俩加在一起就是 2 倍了,这样就有点 “浪费”。

因此,Duck 不必!

duck不必

那咋做呢?😳

删除栈顶元素的做法是:使用堆底元素覆盖堆顶元素,然后对堆进行修复,使用下滤操作。

根据这个启发,在实现 replace 时可以 使用替换元素覆盖堆顶元素,然后进行下滤操作

replace() 方法的完整实现如下(注意部分特殊情况):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@Override
public E replace(E element) {
elementNotNullCheck(element);

E root = null;
if (size == 0) {
elements[0] = element;
size = 1;
} else {
root = elements[0];
elements[0] = element;
siftDown(0);
}

return root;
}

3. 批量建堆

3.1 基本含义

批量建堆(Heapify),就是将一组不满足堆要求的数据形成一个堆。(我自己的理解,可能不大准确😜)

假设现有一组数据,它们是乱的、无规则的,想要把它们构造成一个堆,这就是 批量建堆。

那这好做!🙋

1
2
3
4
5
6
7
public static void main(String[] args) {
int[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
BinaryHeap<Integer> heap = new BinaryHeap<>();
for (int i = 0; i < data.length; i++) {
heap.add(data[i]);
}
}

这样不就完事了?

这么做也确实可以,但是没有必要!

可以但没必要

还有更好的做法:

  • 自上而下的上滤
  • 自下而上的下滤

3.2 自上而下的上滤

现有如下图所示的一组数据,它不满足:任意节点的值总是 大于等于 (或小于等于)其 子节点 的值。因此,它不是一个堆,但可以看成一棵二叉树。

接下来对这组数据进行改造,将其变为一个堆。

批量建堆的数据

首先采用的做法是: 自上而下的上滤

这啥意思呢?就是按照从上到下,从左到右的顺序,对这些数据进行上滤操作。

即:按照 { 30, 34, 73, 60, 68, 43 } 的顺序进行上滤。

进行上滤时第一个元素可以不用进行上滤,因为它已经是第一个元素了,上滤个 🔨 。

使用上述的数据,自上而下的上滤示意图为:

自上而下的上滤示意图

通过示意图可以发现,每进行一次上滤,观察局部都是一个最大堆,比如在第三步中,{73, 30, 34} 就是一个堆。持续进行上滤,直到整个结构都变成堆。

自上而下的上滤的本质是: 每进行一次上滤,就向堆中添加一个元素,堆慢慢长大,最终成为一个“大堆”,与添加 add() 类似。

上述过程可以像这样实现:

1
2
3
for(int i = 1; i < size; i++){
siftUp(i);
}

3.2 自下而上的下滤

自上而下的上滤已经介绍完了,那么自下而上的下滤也就很好理解了。

自下而上的下滤:就是按照从下到上,从右到左的顺序,对这些数据进行下滤操作。

还是使用这样的一组数据:

批量建堆的数据

自下而上的下滤顺序为: {43, 68, 60, 73, 34, 30}

和上滤一样,下滤时也要注意一点: 叶子节点不用进行下滤,因为下滤是使用当前节点和其最大子节点进行交换,叶子节点都没子节点,交换个 🔨 。

使用上述的数据,自下而上的下滤示意图如下:

自下而上的下滤示意图

通过示意图,我们可以发现,每进行一次下滤,观察局部都是一个最大堆。

比如在第二步中,{73, 43} 就是一个堆。

在第三步中,{68, 60, 34} 也是一个堆,这时就差 30 进行下滤了。

最后就和 replace() 的情况一样了,其他部分都是满足堆的结构,只要将首元素下滤后,整个结构就满足堆的结构了。

自下而上的下滤的本质是: 先形成多个较小的堆,然后把这些堆聚在一起,直接形成一个“大堆”。与 remove() 的后半部分类似。

上述过程可以像这样实现:

1
2
3
for(int i = (size >> 1) - 1; i >= 0; i--){
siftDown(i);
}

3.3 效率对比

前文说了,自上而下的上滤相当于添加操作,而自下而上的下滤相当于删除的后半部分。

从对节点的操作数量来看,上滤仅有首节点没进行上滤,下滤则是叶子结点都不进行下滤。

这样一对比,似乎 自下而上的下滤 的效率更高。😕

实际结果也确实如此。😏

通过下图进行对比:

图中的三角形表示一个完全二叉树,将其分成四层,每一层所占的阴影部分面积不一样,面积越大,表示那一层的节点越多

对于自上而下的上滤:第一层进行上滤的高度为 4 层,第二层进行上滤的高度为 3 层 ······

对于自下而上的下滤:第一层进行上滤的高度为 1 层,第二层进行上滤的高度为 2 层 ······

很显然,对于自上而下的上滤来说,有大量的节点进行上滤的高度为 4 层,而对于自下而上的下滤来说,只有第四层节点进行上滤的高度为 4 层。

批量建堆效率对比

因此不难得出:自下而上的下滤的效率更高

3.4 复杂度

先直接上结论:

  • 自上而下的上滤: O(ologn)
  • 自下而上的下滤: O(n)

堆中的数据不是全排序的,是偏序的,就是说数据是稍微有序的,只能保证“任意节点的值总是大于等于 (或小于等于)其 子节点 的值”,但对于节点的“孙子节点”就不好说了。

而自上而下的上滤的复杂度高达 O(ologn),这足以进行全排序了,但得到的结构却是偏序的,那岂不是很浪费?

对这两种复杂度:

  • 自上而下的上滤其实是所有节点的 深度 之和
  • 自下而上的下滤其实是所有节点的 高度 之和

所有节点的深度之和

仅仅是叶子节点,就有将近 n / 2 个,而且每一个叶子节点的深度都是 O(logn) 级别的。

因此,在叶子节点这一块,就达到了 O(nlogn) 级别。

O(nlogn) 的时间复杂度也足以利用排序算法对所有节点进行全排序了。

所有节点的高度之和

假设是满树,节点的总个数为 n ,树高为 h,那么 n = 2h - 1

所有节点的树高之和 H(n) = 20 * (h - 0) + 21 * (h - 1) + 22 * (h - 2) + ··· + 2h-1 * [h - (h - 1)]

H(n) = h * (20 + 21 + 22 + ··· + 2h-1) - [1 * 21 + 2 * 22 + 3 * 23 + ··· + (h - 1) * 2h-1]

H(n) = h * (2h - 1) - [(h - 2) * 2h + 2]

H(n) = h * 2h - h - h * 2h + 2h+1 - 2

H(n) = 2h+1 - h - 2 = 2 * (2h - 1) - h = 2n - h = 2n - log2(n + 1) = O(n)

上述公式推导涉及到一个错位相减,来复习一下高中数学😂

节点高度和公式推导

3.5 拓展思考

前文提到:自上而下的上滤自下而上的下滤 可以进行批量建堆。

那么,以下方法可以进行批量建堆吗?

  • 自上而下的下滤
  • 自下而上的上滤

答案是不行。😝

通过思考【自上而下的上滤】和【自下而上的下滤】的本质就可以得出答案,前者是添加,后者是删除。

而上面提到的两种方式毫无意义而言,因此是不行。

为了便于阅读,给一组数据方便测试:

Heapify拓展思考测试数据

3.6 代码实现

BinaryHeap 类中编写一个构造方法,此构造方法接收一个数组,并利用数组中的数据构建出包含数组数据的堆:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public BinaryHeap(E[] elements, Comparator<E> comparator){
super(comparator);
if (elements == null || elements.length == 0){
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
// 记得将size复制,不然只会存储第一个元素
size = elements.length;
// 保证容量至少为 10
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
// this.elements = elements;
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify();
}
}

在上述代码中,可以发现有一条语句被注释了:this.elements = elements;

使用这条语句的意思是用堆中的数组指向外部的数组,这么做有一个大问题:如果外部数组的数据发生改变,堆内的数据也会发生改变,这显然是不对的。因此只能将外部数据拷贝一份,再进行批量建堆。

由于添加了一个构造方法,需要对其他构造方法进行修改:

1
2
3
4
5
6
7
8
9
10
11
public BinaryHeap(E[] elements){
this(elements, null);
}

public BinaryHeap(Comparator<E> comparator) {
this(null, comparator);
}

public BinaryHeap() {
this(null, null);
}

最后就是 heapify() 方法的代码了,其实也很简单,在前文已经分析过了:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 批量建堆 堆化
*/
private void heapify(){
// 自上而下的上滤
// for (int i = 0; i < size; i++) {
// siftUp(i);
// }
// 自下而上的下滤
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}

3.7 二叉堆完整代码

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
/**
* 二叉堆(最大堆)
*
* @author 默烦
* @date 2020/8/4
*/
public class BinaryHeap<E> extends AbstractHeap<E>{
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;

public BinaryHeap(E[] elements, Comparator<E> comparator){
super(comparator);
if (elements == null || elements.length == 0){
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
// 记得将size复制,不然只会存储第一个元素
size = elements.length;
// 保证容量至少为 10
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
// this.elements = elements;
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify();
}
}

public BinaryHeap(E[] elements){
this(elements,null);
}

public BinaryHeap(Comparator<E> comparator) {
this(null,comparator);
}

public BinaryHeap() {
this(null,null);
}

@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}

@Override
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size + 1);
elements[size++] = element;
siftUp(size - 1);
}

@Override
public E get() { // 获取堆顶元素
// 判断堆是否为空
emptyCheck();
return elements[0];
}

@Override
public E remove() { // 删除堆顶元素
emptyCheck();

int lastIndex = --size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;

siftDown(0);
return root;
}

@Override
public E replace(E element) {
elementNotNullCheck(element);

E root = null;
if (size == 0) {
elements[0] = element;
size = 1;
} else {
root = elements[0];
elements[0] = element;
siftDown(0);
}

return root;
}

/**
* 批量建堆 堆化
*/
private void heapify(){
// 自下而上的下滤
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}

/**
* 让索引为 index 的元素进行下滤
*
* @param index
*/
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
// 第一个叶子节点的索引 = 非叶子节点的数量
while (index < half) { // 必须保证index位置是非叶子节点
/**
* index 位置的节点的子节点有两种情况
* 1. 只有左子节点
* 2. 同时有左子节点、右子节点
*/
// 默认为左子节点的索引
int childIndex = (index << 1) + 1;
E child = elements[childIndex];

// 右子节点索引
int rightIndex = childIndex + 1;
// 选出最大的子节点
if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
// childIndex = rightIndex;
child = elements[childIndex = rightIndex];
}

if (compare(element, child) >= 0) break;
// 将子节点存放到index位置
elements[index] = child;
// 重新设置index
index = childIndex;
}
elements[index] = element;
}

/**
* 让索引为 index 的元素进行上滤
*
* @param index 数组索引
*/
private void siftUp(int index) {
E e = elements[index];
while (index > 0) { // 索引位置节点有父节点时
int pIndex = (index - 1) >> 1; // 获取父节点索引
E p = elements[pIndex];
if (compare(e, p) <= 0) break;

// 将父元素存储在 index 位置
elements[index] = elements[pIndex];
// 重新赋值 index
index = pIndex;
}
elements[index] = e;
}

// 保证要有capacity的容量(不考虑线程安全)
private void ensureCapacity(int capacity) {
// 当前elements.length 为 10,因为默认容量为10
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为新容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}

// 检查二叉堆 size 是否为 0
private void emptyCheck() {
if (size == 0) {
throw new IndexOutOfBoundsException("Heap is empty!");
}
}

private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null!");
}
}
}

4. 举一反三

4.1 构建最小堆

前文实现了一个二叉堆中的最大堆,所谓最大堆,就是指任意节点一定不小于它的子节点。

那么怎么构建一个最小堆呢?🙋

这简单,把最大堆的代码复制一份,然后把里面的比较逻辑改一改,比如在下滤方法 siftDown() 方法中,将大于改成小于,小于改成大于,如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void siftDown(int index) {
E element = elements[index];
int half = size >> 1;
while (index < half) { // 必须保证index位置是非叶子节点
int childIndex = (index << 1) + 1;
E child = elements[childIndex];
int rightIndex = childIndex + 1;
// 最小堆构建,修改比较逻辑
if (rightIndex < size && compare(elements[rightIndex], child) < 0) {
child = elements[childIndex = rightIndex];
}
// 最小堆构建,修改比较逻辑
if (compare(element, child) <= 0) break;
elements[index] = child;
index = childIndex;
}
elements[index] = element;
}

同理,上滤方法 siftUp() 也是同样的修改方式。

这…可以是可以,但是不够优雅。😰

其实还有更简单的方法,堆中的数据都有可比较性,这些数据要么实现 Comparable 接口,要么在构建堆时使用自定义的比较器。堆中对元素进行比较的实现如下:

1
2
3
4
protected int compare(E e1, E e2) {
return comparator != null ? comparator.compare(e1, e2)
: ((Comparable<E>) e1).compareTo(e2);
}

compare() 方法的返回值大于 0 时,表示 e1 比较大;当返回值小于 0 时,表示 e2 比较大;当返回值等于 0 时,表示 e1 和 e2 相等。

对,就是比较器!可以使用比较器:

1
2
3
4
5
6
7
8
9
static void test(){
Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
}

像上述这样使用比较器并重写 compare() 方法后,就相当于为数据指定了一套比较规则。

比较器中 compare() 方法中的 返回值如果大于 0 时,表示 o1 比较大 ;当返回值小于 0 时,表示 o2 比较大;当返回值等于 0 时,表示 o1 和 o2 相等。

假设 o1 为 20,o2 为 10,这个时候 o1 - o2 是大于 0 ,就表示 o1 相对于 o2 是较大的,而 o1 的数值也是大于 o2 的数值的。又假设 o1 为 10,o2 为 20,这个时候 o1 - o2 是小于 0 ,就表示 o1 相对于 o2 是较小的,而 o2 的数值也是大于 o1 的数值的。简单来说,在这种情况下,数值大的数据就比较大

使用这种方式得到的二叉堆如下图:

数值大较大的二叉堆

那么如果换种方式,使用 o2 - o1 呢?即:

1
2
3
4
5
6
7
8
9
10
static void test(){
Integer[] data = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
BinaryTrees.println(heap);
}

假设 o1 为 20,o2 为 10,这个时候 o2 - o1 是小于 0 ,就表示 o1 相对于 o2 是较小的,而 o1 的数值却小于 o2 的数值的。又假设 o1 为 10,o2 为 20,这个时候 o2 - o1 是大于 0 ,就表示 o1 相对于 o2 是较大的,而 o2 的数值却大于 o1 的数值的。简单来说,在这种情况下,数值小的数据就比较大

在以前实现的二叉堆中,默认是最大堆,就是任意节点不小于其子节点,也就是说,任意节点相对于其子节点是较大的。

正因如此,如果使用 o1 - o2 表示数值较大的数据比较大,那么构建出来的最大堆中任意节点的数值是不小于其子节点的,这是个真正意义的最大堆。如果使用 o2 - o1 表示数值较小的数据比较大,那么构建出来的最大堆中任意节点的数值是不大于其子节点,这个时候,与其说是最大堆,不如说是最小堆。

使用 o2 - o1 后得到的二叉堆如下图:

数值小较大的二叉堆

总结

说了那么多,总结一下:

  • BinaryHeap实现的是最大堆,最大堆的任意节点相对于其子节点是较大的
  • 使用比较器后:
    • 返回值为 o1 - o2 时,表示数值较大的数据比较大,那么这时候的二叉堆任意节点的 数值 是大于等于其子节点的 数值,这个堆 看起来就是一个最大堆
    • 返回值为 o2 - o1 时,表示数值较小的数据比较大,那么这时候的二叉堆任意节点的 数值 是小于等于其子节点的 数值,这个堆 看起来就是一个最小堆

默认实现的是最大堆,但可以修改比较方式,让这个堆看起来是一个最大堆或最小堆。

注意: 理解 “数值较大” 和 “节点较大” 的区别,理解 “实现的是最大堆” 和 “看起来是最大堆或最小堆” 的区别。

4.2 Top K 问题

Top K问题:从 n 个整数中,找出最大的前 k 个数。(k 远远小于 n)

有两种解决方式:

  • 使用排序算法进行全排序,需要 O(nlogn) 的时间复杂度
  • 使用二叉堆来解决,需要 O(nlogk) 的时间复杂度

由于 k 远远小于 n,因此第二种方式是更好的,选择使用二叉堆来解决。

具体思路

1、新建一个小顶堆(不是找最大吗?为啥用小顶堆?😕别急,待会解释😎)

2、扫描 n 个整数

  • 先将遍历到的前 k 个数放入堆中
  • 从第 k + 1 个数开始,如果大于堆顶元素,就使用 replace 操作(删除堆顶元素,将第 k + 1 个数添加到堆中)

3、扫描完毕后,堆中剩下的就是最大的前 k 个数

代码实现

假设现有 30 个数,找出其中最大的前 5 个数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void topK() {
// 新建一个小顶堆
BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});

// 找出最大的前k个数
int k = 5;
Integer[] data = {51, 30, 39, 92, 74, 25, 16, 93,
91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
90, 6, 65, 49, 3, 26, 61, 21, 48};
for (int i = 0; i < data.length; i++) {
if (heap.size() < k) { // 前 k个数添加到小顶堆
heap.add(data[i]); // logk
} else if (data[i] > heap.get()) { // 如果是第 k+1个数,并大于堆顶元素
heap.replace(data[i]); // // logk
}
}
// O(nlogk)
}

最终得到的前 5 个数是:76、90、93、92、91

为什么要用小顶堆?

假定小顶堆中的元素是目标数组中最大的几个数。小顶堆的堆顶元素是整个堆中最小的,如果第 k + 1 个数大于堆顶元素,那么它一定该在这个小顶堆中。这个时候删除堆顶元素,将第 k + 1 个数添加到堆中,使得原本这个堆中的最小元素变大了,也保持小顶堆中的元素是目标数组中最大的几个数。一直循环扫描,堆中最小的元素不断变大,最后堆中的元素一定真正是那 n 个数中最大的前 k 个数。

使用堆解决 Top K 问题的时间复杂度为 O(nlogk) 是怎么计算的?

二叉堆添加元素的时间复杂度为 O(logn),其中的 n 表示堆中的元素。在这个问题中,堆中元素是 k 个,因此 add() 方法的时间复杂度为 O(logk)。对于 replace() 方法也是如此,时间复杂度为 O(logk)。在上述代码中涉及两个判断,这两个判断中一个判断成功后调用 add() 方法,另一个判断成功后调用 replace() 方法,假设在最坏情况下,不是调用 add() 就是调用 replace(),那么这样的时间复杂度为 O(nlogk),n 为数据总数。最终,使用堆解决 Top K 问题的时间复杂度就为 O(nlogk)

如果是找出最小的前 k 个数应该怎么办?

使用大顶堆,其他操作一样,只不过第 k + 1 个元素小于堆顶元素时,使用 replace 操作。