堆
以大顶堆为例，相对于之前的优先级队列，增加了堆化等方法
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
| public class MaxHeap {
int[] array;
int size;
public MaxHeap(int capacity) {
this.array = new int[capacity];
}
public int peek() {
return array[0];
}
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
public int poll(int index) {
int deleted = array[index];
up(Integer.MAX_VALUE, index);
poll();
return deleted;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
up(offered, size);
size++;
return true;
}
private void up(int offered, int index) {
int child = index;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
private void heapify() {
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max]) {
max = left;
}
if (right < size && array[right] > array[max]) {
max = right;
}
if (max != parent) {
swap(max, parent);
down(max);
}
}
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
public static void main(String[] args) {
int[] array = {2, 3, 1, 7, 6, 4, 5};
MaxHeap heap = new MaxHeap(array);
System.out.println(Arrays.toString(heap.array));
while (heap.size > 1) {
heap.swap(0, heap.size - 1);
heap.size--;
heap.down(0);
}
System.out.println(Arrays.toString(heap.array));
}
}
|
建堆
Floyd 建堆算法作者（也是之前龟兔赛跑判环作者）：
- 找到最后一个非叶子节点
- 从后向前，对每个节点执行下潜
一些规律
- 一棵满二叉树节点个数为 2h−1，如下例中高度 h=3 节点数是 23−1=7
- 非叶子节点范围为 [0,size/2−1]
算法时间复杂度分析
下面看交换次数的推导：设节点高度为 3
|
本层节点数 |
高度 |
下潜最多交换次数（高度-1） |
| 4567 这层 |
4 |
1 |
0 |
| 23这层 |
2 |
2 |
1 |
| 1这层 |
1 |
3 |
2 |
每一层的交换次数为：节点个数∗此节点交换次数，总的交换次数为
4∗0+2∗1+1∗228∗0+48∗1+88∗2218∗0+228∗1+238∗2
即
i=1∑h(2i2h∗(i−1))
在 https://www.wolframalpha.com/ 输入
1
| Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]
|
推导出
2h−h−1
其中 2h≈n，h≈log2n，因此有时间复杂度 O(n)
习题
E01. 堆排序
算法描述
- heapify 建立大顶堆
- 将堆顶与堆底交换（最大元素被交换到堆底），缩小并下潜调整堆
- 重复第二步直至堆里剩一个元素
可以使用之前课堂例题的大顶堆来实现
1
2
3
4
5
6
7
8
9
10
| int[] array = {1, 2, 3, 4, 5, 6, 7};
MaxHeap maxHeap = new MaxHeap(array);
System.out.println(Arrays.toString(maxHeap.array));
while (maxHeap.size > 1) {
maxHeap.swap(0, maxHeap.size - 1);
maxHeap.size--;
maxHeap.down(0);
}
System.out.println(Arrays.toString(maxHeap.array));
|
E02. 数组中第K大元素-Leetcode 215
小顶堆（可删去用不到代码）
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
| class MinHeap {
int[] array;
int size;
public MinHeap(int capacity) {
array = new int[capacity];
}
private void heapify() {
for (int i = (size >> 1) - 1; i >= 0; i--) {
down(i);
}
}
public int poll() {
swap(0, size - 1);
size--;
down(0);
return array[size];
}
public int poll(int index) {
swap(index, size - 1);
size--;
down(index);
return array[size];
}
public int peek() {
return array[0];
}
public boolean offer(int offered) {
if (size == array.length) {
return false;
}
up(offered);
size++;
return true;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) >> 1;
if (offered < array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
private void down(int parent) {
int left = (parent << 1) + 1;
int right = left + 1;
int min = parent;
if (left < size && array[left] < array[min]) {
min = left;
}
if (right < size && array[right] < array[min]) {
min = right;
}
if (min != parent) {
swap(min, parent);
down(min);
}
}
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
|
题解
1
2
3
4
5
6
7
8
9
10
11
12
| public int findKthLargest(int[] numbers, int k) {
MinHeap heap = new MinHeap(k);
for (int i = 0; i < k; i++) {
heap.offer(numbers[i]);
}
for (int i = k; i < numbers.length; i++) {
if(numbers[i] > heap.peek()){
heap.replace(numbers[i]);
}
}
return heap.peek();
}
|
求数组中的第 K 大元素，使用堆并不是最佳选择，可以采用快速选择算法
E03. 数据流中第K大元素-Leetcode 703
上题的小顶堆加一个方法
1
2
3
4
5
6
| class MinHeap {
public boolean isFull() {
return size == array.length;
}
}
|
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class KthLargest {
private MinHeap heap;
public KthLargest(int k, int[] nums) {
heap = new MinHeap(k);
for(int i = 0; i < nums.length; i++) {
add(nums[i]);
}
}
public int add(int val) {
if(!heap.isFull()){
heap.offer(val);
} else if(val > heap.peek()){
heap.replace(val);
}
return heap.peek();
}
}
|
求数据流中的第 K 大元素，使用堆最合适不过
E04. 数据流的中位数-Leetcode 295
可以扩容的 heap, max 用于指定是大顶堆还是小顶堆
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
| public class Heap {
int[] array;
int size;
boolean max;
public int size() {
return size;
}
public Heap(int capacity, boolean max) {
this.array = new int[capacity];
this.max = max;
}
public int peek() {
return array[0];
}
public int poll() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
public void offer(int offered) {
if (size == array.length) {
grow();
}
up(offered);
size++;
}
private void grow() {
int capacity = size + (size >> 1);
int[] newArray = new int[capacity];
System.arraycopy(array, 0,
newArray, 0, size);
array = newArray;
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
boolean cmp = max ? offered > array[parent] : offered < array[parent];
if (cmp) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
public Heap(int[] array, boolean max) {
this.array = array;
this.size = array.length;
this.max = max;
heapify();
}
private void heapify() {
for (int i = size / 2 - 1; i >= 0; i--) {
down(i);
}
}
private void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int min = parent;
if (left < size && (max ? array[left] > array[min] : array[left] < array[min])) {
min = left;
}
if (right < size && (max ? array[right] > array[min] : array[right] < array[min])) {
min = right;
}
if (min != parent) {
swap(min, parent);
down(min);
}
}
private void swap(int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
|
题解
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 Heap left = new Heap(10, false);
private Heap right = new Heap(10, true);
public void addNum(int num) {
if (left.size() == right.size()) {
right.offer(num);
left.offer(right.poll());
} else {
left.offer(num);
right.offer(left.poll());
}
}
public double findMedian() {
if (left.size() == right.size()) {
return (left.peek() + right.peek()) / 2.0;
} else {
return left.peek();
}
}
|
本题还可以使用平衡二叉搜索树求解，不过代码比两个堆复杂
10.基础数据结构-阻塞队列
12.基础数据结构-二叉树
