algo-heap

堆 (优先队列)

基本堆操作:

1
2
3
4
5
6
public interface PriorityQueue<T> {
public void add(T value);
public boolean isEmpty();
public T peek();
public T remove();
}

动画演示: https://visualgo.net/en/heap


我们没用 array[0] 元素。


add(T value):

1
array[++size] = value;

然后在一步一步与父元素做对比向上冒泡:

1
2
3
4
5
6
7
8
9
10
protected void bubbleUp() {
int index = this.size;

while (hasParent(index)
&& (parent(index).compareTo(array[index]) > 0)) {
// parent/child are out of order; swap them
swap(index, parentIndex(index));
index = parentIndex(index);
}
}

时间复杂度: O(log N)


T remove():

1
2
3
array[1] = array[size];
array[size] = null;
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
protected void bubbleDown() {
int index = 1;

// bubble down
while (hasLeftChild(index)) {
// which of my children is smaller?
int smallerChild = leftIndex(index);

// bubble with the smaller child, if I have a smaller child
if (hasRightChild(index)
&& array[leftIndex(index)].compareTo(array[rightIndex(index)]) > 0) {
smallerChild = rightIndex(index);
}

if (array[index].compareTo(array[smallerChild]) > 0) {
swap(index, smallerChild);
} else {
// otherwise, get outta here!
break;
}

// make sure to update loop counter/index of where last el is put
index = smallerChild;
}
}

推荐文章