二叉堆

二叉堆的应用场景很多,例如外排序多路归并,TopK问题,优先队列,排序

算法思想

堆是一个完全二叉树,也就是树的最后一层,节点都是靠左的,其上的层,都是满的。

另外一个性质,小(大)根堆除了根节点外的每一个节点的父节点都比该节点小(大)或相等。

插入

将待插入节点放置在树的最后,也就是如果最后一层不满,就靠左摆放,否则就增加新的一层,保证第一条性质。

插入之后,堆的第二条性质,有可能被打破了,(以下都以小根堆为例)该节点比其父节点小,交换其与父子节点,然后接着如此处理,直到该节点大于等于父节点,或者到达根节点。形象地看,就是向上冒泡。

删除

二叉堆只能删除掉根节点。

删除根节点后,将二叉堆最后一个节点放置到根处。

这时候第二条性质,可能被打破了,从根节点向下调整,若两个儿子都不小于当前节点,则结束,否则,找到儿子中小的那个与之交换,然后继续处理。

可视化

二叉堆的应用场景很多,例如外排序多路归并,TopK问题,优先队列,排序

算法思想

堆是一个完全二叉树,也就是树的最后一层,节点都是靠左的,其上的层,都是满的。

另外一个性质,小(大)根堆除了根节点外的每一个节点的父节点都比该节点小(大)或相等。

插入

将待插入节点放置在树的最后,也就是如果最后一层不满,就靠左摆放,否则就增加新的一层,保证第一条性质。

插入之后,堆的第二条性质,有可能被打破了,(以下都以小根堆为例)该节点比其父节点小,交换其与父子节点,然后接着如此处理,直到该节点大于等于父节点,或者到达根节点。形象地看,就是向上冒泡。

删除

二叉堆只能删除掉根节点。

删除根节点后,将二叉堆最后一个节点放置到根处。

这时候第二条性质,可能被打破了,从根节点向下调整,若两个儿子都不小于当前节点,则结束,否则,找到儿子中小的那个与之交换,然后继续处理。

演示程序


示例代码

虽然是树,但是由于完全二叉树的性质,可以很方便地使用数组模拟树结构,数组的头一个元素不用,下标1对应树根,对于节点i,i<<1为左儿子,i<<1|1为右儿子,i>>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
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
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
import java.util.stream.Stream;
public class Heap<E> {
public static void main(String... args) throws Exception {
Heap<Double> heap = new Heap<Double>(DOUBLE_LITTLE_ROOT);
Random r = new Random();
Stream.generate(() -> r.nextDouble()).limit(10).forEach(val -> heap.push(val));
System.out.println(heap.size);
while (!heap.isEmpty()) {
System.out.println(heap.pop());
}
}
public static final Comparator<Integer> INTEGER_LITTLE_ROOT = (x, y) -> ((Integer) x).compareTo((Integer) y);
public static final Comparator<Integer> INTEGER_BIG_ROOT = (x, y) -> ((Integer) y).compareTo((Integer) x);
public static final Comparator<Double> DOUBLE_LITTLE_ROOT = (x, y) -> ((Double) x).compareTo((Double) y);
public static final Comparator<Double> DOUBLE_BIT_ROOT = (x, y) -> ((Double) y).compareTo((Double) x);
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private Comparator<E> cmp;
private Object[] elementData;
private int size;
public Heap(int initialCapacity, Comparator<E> cmp) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
this.cmp = cmp;
size = 1;
}
public Heap(Comparator<E> cmp) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
this.cmp = cmp;
size = 1;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
@SuppressWarnings("unchecked")
public void push(E val) {
ensureCapacityInternal(size + 1);
elementData[size] = val;
int pos = size++;
while ((pos >> 1) != 0) {
if (cmp.compare((E) elementData[pos], (E) elementData[pos >> 1]) < 0) {
swap(elementData, pos, pos >> 1);
pos = pos >> 1;
} else
break;
}
}
public boolean isEmpty() {
return size == 1;
}
@SuppressWarnings("unchecked")
public E pop() throws Exception {
if (size == 1)
throw new Exception("heap is empty");
E top = (E) elementData[1];
elementData[1] = elementData[--size];
int pos = 1;
while (pos < size) {
int sonPos = pos << 1;
if (sonPos >= size)
break;
if (cmp.compare((E) elementData[sonPos | 1], (E) elementData[sonPos]) < 0 && (sonPos | 1) < size) {
sonPos = sonPos | 1;
}
if (cmp.compare((E) elementData[pos], (E) elementData[sonPos]) <= 0) {
break;
}
swap(elementData, pos, sonPos);
pos = sonPos;
}
return top;
}
private void swap(Object[] elementData, int a, int b) {
Object tmp = elementData[a];
elementData[a] = elementData[b];
elementData[b] = tmp;
}
public int size() {
return size-1;
}
}