堆(Heap)/优先队列的实现

堆(Heap)

完全二叉堆

完全二叉堆就是用完全二叉树实现的堆

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

因为完全二叉树的结点都是相邻的

如果任意结点的值总是>=子结点的值,称为大根堆,最大堆,大顶堆,最大值都在根节点

如果任意结点的值总是<=子结点的值,称为小根堆,最小堆,小顶堆,最小值都在根节点

image-20220401152952323

基本的接口设计

image-20220401153056702

大根堆的实现

抽象类

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
@SuppressWarnings("unchecked")
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);
}
}

实现类

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
214
215
216
217
218
219
220
/**
* 大顶堆
*/
@SuppressWarnings("unchecked")
public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo {
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 = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
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++;
} else {
root = elements[0];
elements[0] = element;
siftDown(0);
}
return root;
}

/**
* 批量建堆
*/
private void heapify() {
// 自上而下的上滤
// for (int i = 1; i < size; i++) {
// siftUp(i);
// }

// 自下而上的下滤
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;
// 第一个叶子节点的索引 == 非叶子节点的数量
// index < 第一个叶子节点的索引
// 必须保证index位置是非叶子节点
while (index < half) {
// index的节点有2种情况
// 1.只有左子节点
// 2.同时有左右子节点

// 默认为左子节点跟它进行比较
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;

// 将子节点存放到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) return;
//
// // 交换index、pindex位置的内容
// E tmp = elements[index];
// elements[index] = elements[pindex];
// elements[pindex] = tmp;
//
// // 重新赋值index
// index = pindex;
// }
E element = elements[index];
while (index > 0) {
int parentIndex = (index - 1) >> 1;
E parent = elements[parentIndex];
if (compare(element, parent) <= 0) break;

// 将父元素存储在index位置
elements[index] = parent;

// 重新赋值index
index = parentIndex;
}
elements[index] = element;
}

private void ensureCapacity(int capacity) {
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;
}

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");
}
}

@Override
public Object root() {
return 0;
}

@Override
public Object left(Object node) {
int index = ((int)node << 1) + 1;
return index >= size ? null : index;
}

@Override
public Object right(Object node) {
int index = ((int)node << 1) + 2;
return index >= size ? null : index;
}

@Override
public Object string(Object node) {
return elements[(int)node];
}
}

快速建堆

自上而下的上滤

等价于挨个元素进行添加

1
2
3
for (int i = 1; i < elements.length; i++) {
siftUp(i);
}

自下而上的下滤

类似于删除,从下而上慢慢的建成堆

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

性能对比

image-20220401190340537

自上而下的下滤的建堆,比较多的结点在做工作量少的事情,自上而下的上滤正好相反

堆的应用场景

优先级队列

image-20220401195245053

Java里的优先队列是PriorityQueue

可以用来解决Top k问题

在无序数组中找到第k个,最大/最小的元素