|
6 | 6 | ## 1. 二叉堆 |
7 | 7 |
|
8 | 8 | 二叉堆是一棵完全二叉树，如下图： |
9 | | - |
| 9 | + |
| 10 | + |
| 11 | +完全二叉树性质如下： |
| 12 | +- 元素顺序排列成树的形状 |
| 13 | +- 堆中某节点的值总是不大于其父节点的值 |
| 14 | +- 上图这种父亲节点值最大，则表示的是最大堆 |
| 15 | + |
| 16 | +同理，可以让父亲节点值最小，则可以被称为最小堆。 |
10 | 17 |
|
11 | 18 | 这里，给出一个最大堆和最小堆的定义： |
12 | 19 |
|
|
27 | 34 | 0 1 2 3 4 5 6 7 8 9 |
28 | 35 | ``` |
29 | 36 | 将数组转化为二叉堆： |
30 | | - |
| 37 | + |
31 | 38 |
|
32 | 39 | 对于上面的二叉堆，有以下三个比较重要的公式： |
33 | 40 |
|
34 | 41 | ``` |
| 42 | +(i从0开始计算） |
35 | 43 | parent(i) = (i - 1) / 2 求当前节点的父节点的索引 |
36 | 44 | left child(i) = 2 * i + 1 求当前节点的左子节点的索引 |
37 | 45 | right child(i) = 2 * i + 2 求当前节点的右子节点的索引 |
38 | 46 | ``` |
39 | 47 |
|
| 48 | +构建代码： |
| 49 | +``` |
| 50 | +public class MaxHeap { |
| 51 | +
|
| 52 | + /** |
| 53 | + * 注意，由于数组元素默认值为0，所以堆中元素不可为0 |
| 54 | + */ |
| 55 | + private int[] data; |
| 56 | +
|
| 57 | + /** |
| 58 | + * 记录数组中元素个数 |
| 59 | + */ |
| 60 | + private int size; |
| 61 | +
|
| 62 | + /** |
| 63 | + * 数组容量（初始化大小） |
| 64 | + */ |
| 65 | + private int capacity; |
| 66 | +
|
| 67 | + public MaxHeap(int capacity) { |
| 68 | + data = new int[capacity]; |
| 69 | + this.capacity = capacity; |
| 70 | + size = 0; |
| 71 | + } |
| 72 | + public MaxHeap() { |
| 73 | + data = new int[10]; |
| 74 | + capacity = 10; |
| 75 | + size = 0; |
| 76 | + } |
| 77 | +
|
| 78 | + // ================================ heapify(二叉堆化) ======================== |
| 79 | +
|
| 80 | + public MaxHeap(int[] data) { |
| 81 | + int n = data.length; |
| 82 | + this.data = new int[n+1]; |
| 83 | + capacity = n; |
| 84 | +
|
| 85 | + for (int i = 0; i < n; i++) { |
| 86 | + this.data[i+1] = data[i]; |
| 87 | + } |
| 88 | + size = n; |
| 89 | +
|
| 90 | + // 这里需要注意，size / 2 得到的索引是二叉堆中最后一个非叶子节点。 |
| 91 | + for (int i = size / 2; i > 0; i++) { |
| 92 | + siftDown(i); |
| 93 | + } |
| 94 | + } |
| 95 | +
|
| 96 | + /** |
| 97 | + * 返回堆中真实存在元素个数 |
| 98 | + * @return |
| 99 | + */ |
| 100 | + public int size() { |
| 101 | + return size; |
| 102 | + } |
| 103 | +
|
| 104 | + /** |
| 105 | + * 返回堆中是否为空 |
| 106 | + * @return |
| 107 | + */ |
| 108 | + public boolean isEmpty() { |
| 109 | + return size == 0; |
| 110 | + } |
| 111 | +
|
| 112 | + /** |
| 113 | + * 返回index索引其父亲节点 |
| 114 | + * @param index |
| 115 | + * @return |
| 116 | + */ |
| 117 | + private int parent(int index) { |
| 118 | + if (index == 0) { |
| 119 | + throw new IllegalArgumentException("index-0 doesn't have parent"); |
| 120 | + } |
| 121 | + return (index - 1) / 2; |
| 122 | + } |
| 123 | +
|
| 124 | + /** |
| 125 | + * 返回index索引的左子节点 |
| 126 | + * @param index |
| 127 | + * @return |
| 128 | + */ |
| 129 | + private int leftChild(int index) { |
| 130 | + return index * 2 + 1; |
| 131 | + } |
| 132 | +
|
| 133 | + /** |
| 134 | + * 返回index索引的右子节点 |
| 135 | + * @param index |
| 136 | + * @return |
| 137 | + */ |
| 138 | + private int rightChild(int index) { |
| 139 | + return index * 2 + 2; |
| 140 | + } |
| 141 | +
|
| 142 | + // ================================ 上浮 siftUp ======================== |
| 143 | +
|
| 144 | + /** |
| 145 | + * 向堆中添加元素 |
| 146 | + */ |
| 147 | + public void add(int i) { |
| 148 | + // 注意size和capacity的关系，判断是否容量已经满了 |
| 149 | + // 向数组最后一位添加新元素 |
| 150 | + data[size] = i; |
| 151 | + siftUp(size++); |
| 152 | + } |
| 153 | +
|
| 154 | + /** |
| 155 | + * 上浮过程 |
| 156 | + * @param k |
| 157 | + */ |
| 158 | + private void siftUp(int k) { |
| 159 | + // k 索引大于0，并且k索引元素值大于k父亲节点元素值 |
| 160 | + while (k > 0 && data[parent(k)] < data[k]) { |
| 161 | + // k和parent(k)互换元素 |
| 162 | + swap(data, k, parent(k)); |
| 163 | + // 向上移动，让k为parent(k)再进行判断 |
| 164 | + k = parent(k); |
| 165 | + } |
| 166 | + } |
| 167 | +
|
| 168 | + // ================================ 下浮 siftDown ======================== |
| 169 | +
|
| 170 | + /** |
| 171 | + * 获取堆中最大元素 |
| 172 | + * @return |
| 173 | + */ |
| 174 | + public int findMax() { |
| 175 | + if (size == 0) { |
| 176 | + throw new IllegalArgumentException("Can't find Max value!"); |
| 177 | + } |
| 178 | + return data[0]; |
| 179 | + } |
| 180 | +
|
| 181 | + /** |
| 182 | + * 取出堆中最大元素 |
| 183 | + * @return |
| 184 | + */ |
| 185 | + public int extractMax() { |
| 186 | + int max = findMax(); |
| 187 | + swap(data, 0, size - 1); |
| 188 | + data[size - 1] = 0; |
| 189 | + siftDown(0); |
| 190 | + return max; |
| 191 | + } |
| 192 | +
|
| 193 | + /** |
| 194 | + * 下沉操作 |
| 195 | + * @param k |
| 196 | + */ |
| 197 | + private void siftDown(int k) { |
| 198 | + // 左子节点比数组元素小，则表示有子节点 |
| 199 | + while (leftChild(k) < size()) { |
| 200 | + int j = leftChild(k); |
| 201 | + // 如果k的有右子节点 |
| 202 | + if (j + 1 < size() && data[j + 1] > data[j]) { |
| 203 | + // 所以让j为右子节点 |
| 204 | + // j = rightChild(k); 同 |
| 205 | + j++; |
| 206 | + } |
| 207 | + // 此时data[k] 比leftChild和rightChild中的最大值都要大 |
| 208 | + if (data[k] > data[j]) { |
| 209 | + break; |
| 210 | + } |
| 211 | + // leftChild和rightChild都比data[k]大，在互换之后，继续下一轮判断 |
| 212 | + swap(data, k, j); |
| 213 | + // 互换位置，继续下一轮判断 |
| 214 | + k = j; |
| 215 | + } |
| 216 | + } |
| 217 | +
|
| 218 | + // ================================ 替换操作 ======================== |
| 219 | +
|
| 220 | + private void swap(int[] arr, int i, int j) { |
| 221 | + int tmp = arr[i]; |
| 222 | + arr[i] = arr[j]; |
| 223 | + arr[j] = tmp; |
| 224 | + } |
| 225 | +
|
| 226 | + public static void main(String[] args) { |
| 227 | + int n = 100; |
| 228 | + MaxHeap maxHeap = new MaxHeap(n); |
| 229 | + Random random = new Random(); |
| 230 | + for (int i = 0; i < n; i++) { |
| 231 | + maxHeap.add(random.nextInt(1000)); |
| 232 | + } |
| 233 | + int[] result = new int[n]; |
| 234 | + for (int i = 0; i < n; i++) { |
| 235 | + result[i] = maxHeap.extractMax(); |
| 236 | + } |
| 237 | + // 测试是否是顺序的 |
| 238 | + for (int j = 1; j < n; j++) { |
| 239 | + if (result[j-1] < result[j]) { |
| 240 | + throw new IllegalArgumentException("Error!"); |
| 241 | + } |
| 242 | + } |
| 243 | + } |
| 244 | +} |
| 245 | +``` |
| 246 | + |
| 247 | +上浮Sift Up过程如下图： |
| 248 | + |
| 249 | + |
| 250 | +插入的新节点与父亲节点比较大小，如果比父亲节点大，则进行swap交换，直至到符合完全二叉树性质。 |
| 251 | + |
| 252 | +取出最大值以及下沉过程： |
| 253 | +先取出最大值，让数组最后一位元素替换堆顶元素，然后往下沉。 |
| 254 | + |
| 255 | + |
| 256 | + |
| 257 | + |
| 258 | +heapify二叉堆化，即从最后一个非叶子节点开始siftDown，即图中蓝色图表示的节点元素。 |
| 259 | + |
| 260 | + |
| 261 | + |
40 | 262 | ## 2. 优先队列 |
41 | 263 |
|
| 264 | +> 普通队列：先进先出，后进后出； |
| 265 | +
|
| 266 | +> 优先队列：出队顺序和入队顺序无关；和优先级有关； |
| 267 | +
|
| 268 | +在Windows操作系统中，任务管理器的任务就是根据优先级别来进行管理的，**动态选择优先级最高的任务执行。** |
| 269 | + |
42 | 270 | 普通线性结构和顺序线性结构对比 |
43 | 271 | | | 入队 | 出队（拿出最大元素） | |
44 | 272 | | :----: | :-----: | :--------: | |
45 | 273 | | 普通线性结构 | O(1) | O(n) | |
46 | 274 | | 顺序线性结构 | O(n) | O(1) | |
47 | 275 | | 堆 | O(logn) | O(logn) | |
48 | 276 |
|
| 277 | +对于线性结构出队时（数组），需要扫描整个队列；对于顺序线性结构（链表），入队时由于需要维持顺序性则需要扫描整个队列； |
| 278 | + |
49 | 279 | **普通线性结构**入队O(1)分析，因为入队不考虑顺序性，所以排在队尾即可。 |
50 | 280 |
|
51 | 281 | **顺序线性结构**入队O(n)分析，入队需要考虑顺序性，需要进行调度。 |
0 commit comments