Skip to content

Commit 8a9554d

Browse files
fengyuan-liangfengyuan-liang
committed
heapify study
1 parent 92d7f89 commit 8a9554d

5 files changed

Lines changed: 403 additions & 14 deletions

File tree

‎AlgorithmAndDataStructure/13-二叉堆.md‎

Lines changed: 162 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@
4949
观察索引`i`我们可以发现一些规律
5050

5151
- 如果`i = 0`，它就是`根结点`
52-
- 如果`i > 0`，它的父结点编号为`floor(i - 1) / 2`
52+
- 如果`i > 0`，它的父结点编号为`floor((i - 1) / 2)`
5353
- 如果`2i + 1 <= n - 1`，它的左子节点编号为`2i + 1`（n为堆元素的个数）
5454
- 如果`2i + 1 > n - 1`，它无左子节点
5555
- 如果`2i + 2 <= n - 1`，它的右子节点编号为`2i + 2`
@@ -59,6 +59,21 @@
5959

6060
### 1.3 堆（Heap）
6161

62+
>堆（Heap）是一种树状的数据结构（不要跟内存模型中的`堆空间`混淆），常见的堆有：
63+
>
64+
>- 二叉堆（Binary Heap，完全二叉堆）
65+
>- 多叉堆（D-heap、D-ary Heap）
66+
>- 索引堆（Index Heap）
67+
>- 二项堆（Binomial Heap）
68+
>- 斐波拉契堆（Fibonacci Heap）
69+
>- 左倾堆（Leftist Heap，左式堆）
70+
>- 斜堆（Skew Heap）
71+
>
72+
>堆最重要的性质是：**任意结点的值总是大于或小于`子结点`的值**
73+
>
74+
>- 如果任意结点的值总是`大于`子结点，称为：最大堆、大根堆、大顶堆
75+
>- 如果任意结点的值总是`小于`子结点，称为：最小堆、小根堆、小顶堆
76+
6277
## 2. 实现
6378

6479
### 2.1 二叉堆基本接口
@@ -85,7 +100,7 @@ E replace(E element); // 删除堆顶元素的同时插入一个新元素
85100

86101
![image-20230519231051588](https://cdn.fengxianhub.top/resources-master/202305192310845.png)
87102

88-
当时显然这样是不对的，不能满足二叉堆的性质，所以我们需要做的就是`让添加的元素跟父结点进行比较`，因为二叉堆性质就是父结点要比子结点大，即结点`43`要和`14`、`80`，进行比较，如果比子结点小，即交换位置
103+
当然显然这样是不对的，不能满足二叉堆的性质，所以我们需要做的就是`让添加的元素跟父结点进行比较`，因为二叉堆性质就是父结点要比子结点大，即结点`43`要和`14`、`80`，进行比较，如果比子结点小，即交换位置
89104

90105
| 0 | 1 | 2 | `3` | 4 | 5 | 6 | 7 | 8 | 9 | `10` |
91106
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
@@ -124,7 +139,7 @@ private void siftUp(int index) {
124139
// 父结点编号为`floor(i - 1) / 2`
125140
int parentIndex = (index - 1) >> 1;
126141
if (compare(elements[index], elements[parentIndex]) <= 0) {
127-
return;
142+
break;
128143
}
129144
// 交换元素
130145
E tmp = elements[parentIndex];
@@ -161,6 +176,31 @@ public void TestSiftUp() {
161176
50 38
162177
```
163178

179+
当然交换时候的代码还可以再优化一下
180+
181+
```java
182+
/**
183+
* 让index上的元素进行上滤
184+
*
185+
* @param index 元素在数组中的索引
186+
*/
187+
private void siftUp(int index) {
188+
E element = elements[index];
189+
while (index > 0) {
190+
int parentIndex = (index - 1) >> 1;
191+
E parent = elements[parentIndex];
192+
if (compare(element, parent) <= 0) break;
193+
// 将父元素存储在index位置
194+
elements[index] = parent;
195+
// 重新赋值index
196+
index = parentIndex;
197+
}
198+
elements[index] = element;
199+
}
200+
```
201+
202+
203+
164204
完整代码：
165205

166206
```java
@@ -244,19 +284,17 @@ public class BinaryHeap<E> implements Heap<E>, BinaryTreeInfo {
244284
* @param index 元素在数组中的索引
245285
*/
246286
private void siftUp(int index) {
287+
E element = elements[index];
247288
while (index > 0) {
248-
// 检查父结点是否小于该元素
249-
// 父结点编号为`floor(i - 1) / 2`
250289
int parentIndex = (index - 1) >> 1;
251-
if (compare(elements[index], elements[parentIndex]) <= 0) {
252-
return;
253-
}
254-
// 交换元素
255-
E tmp = elements[parentIndex];
256-
elements[parentIndex] = elements[index];
257-
elements[index] = tmp;
290+
E parent = elements[parentIndex];
291+
if (compare(element, parent) <= 0) break;
292+
// 将父元素存储在index位置
293+
elements[index] = parent;
294+
// 重新赋值index
258295
index = parentIndex;
259296
}
297+
elements[index] = element;
260298
}
261299

262300
@SuppressWarnings("unchecked")
@@ -344,7 +382,7 @@ E remove(); // 删除堆顶元素
344382

345383
在下滤的过程中，我们需要注意要下滤的结点必须要有子结点，即不能是叶子结点，根据完全二叉树的性质：
346384

347-
- 如果当前结点为叶子结点，那么后面的结点也都是叶子节点
385+
- **如果当前结点为叶子结点，那么后面的结点也都是叶子节点**
348386

349387
![image-20230523211245733](https://cdn.fengxianhub.top/resources-master/202305232112037.png)
350388

@@ -434,7 +472,118 @@ public void TestSiftUp() {
434472
15
435473
```
436474

475+
### 2.4 replace逻辑
476+
477+
>`replace`逻辑是先删除堆顶元素，然后再将要替换的元素放入堆中（相当于将堆顶元素替换，然后下滤）
478+
479+
我们可以先调用`remove()`方法，再调用`add()`方法，但是这样时间复杂度有两个`log(n)`，所以我们可以这样写：
480+
481+
```java
482+
public E replace(E element) {
483+
checkElementNotNull(element);
484+
E root = null;
485+
if (size == 0) {
486+
elements[0] = element;
487+
size++;
488+
} else {
489+
root = elements[0];
490+
elements[0] = element;
491+
siftDown(0);
492+
}
493+
return root;
494+
}
495+
```
496+
497+
### 2.5 Heapify批量建堆
498+
499+
>什么是`Heapify`批量建堆呢？
500+
>
501+
>我们将无序的数组快速转换为堆的过程称之为`Heapify`（批量建堆）
502+
503+
我们第一时间想到的肯定是直接调用add方法，比如这样：
504+
505+
```java
506+
@Test
507+
public void TestHeapify() {
508+
BinaryHeap<Integer> heap = new BinaryHeap<>();
509+
int[] arr = new int[]{75, 57, 65, 13, 34, 79, 9, 23, 31, 27, 7, 3, 37, 90, 48, 95, 11, 32, 41};
510+
for (int i : arr) {
511+
heap.add(i);
512+
}
513+
BinaryTrees.println(heap);
514+
}
515+
// 打印
516+
┌───────95──────┐
517+
│ │
518+
┌────90────┐ ┌──79──┐
519+
│ │ │ │
520+
┌───57──┐ ┌─34─┐ ┌─65─┐ ┌─75─┐
521+
│ │ │ │ │ │ │ │
522+
┌─31─┐ ┌─41─┐ 27 7 3 37 9 48
523+
│ │ │ │
524+
13 11 23 32
525+
```
526+
527+
这样当然可以，其实也就相当于`自上而下的上滤`，对于批量建堆，我们一般有两种办法：
528+
529+
- 自上而下的上滤
530+
- 自下而上的下滤
531+
532+
#### 2.5.1 自上而下的上滤
533+
534+
自上而下的上滤很简单，只需要从第二个元素开始每个元素都进行上滤操作（第一个元素不需要）
535+
536+
整个过程是这样的
537+
538+
![image-20230611002722242](https://cdn.fengxianhub.top/resources-master/202306110027606.png)
539+
540+
伪代码如下：
541+
542+
```java
543+
// 注意这里i是从1开始的哦
544+
for(int i = 1; i < size; i++) {
545+
siftUp(i);
546+
}
547+
```
437548

549+
#### 2.5.2 自下而上的下滤
550+
551+
自下而上的下滤的过程也比较简单，从最后一个元素开始下滤，但是这里需要注意的是，叶子结点是不需要下滤的，因为不能往下了已经，所以关键代码是：
552+
553+
![image-20230611003356655](https://cdn.fengxianhub.top/resources-master/202306110033820.png)
554+
555+
关键代码如下：
556+
557+
```java
558+
private void heapify() {
559+
// 自下而上的下滤
560+
for (int i = (size >> 1) - 1; i >= 0; i--) {
561+
siftDown(i);
562+
}
563+
}
564+
```
565+
566+
#### 2.5.3 两种方式对比
567+
568+
两种方式进行批量建堆的时间复杂度如下，可以看出由于在`自下而上的下滤`中，叶子结点是不需要进行下滤操作的，并且只有尽可能少的结点需要完成尽可能复杂的`下滤`操作，所以时间复杂度较优
569+
570+
为什么`自上而下的上滤`复杂度比较高呢？这是因为相当于做了`全排序`，但是二叉堆其实是`偏序`的
571+
572+
![image-20230611131743128](https://cdn.fengxianhub.top/resources-master/202306111317440.png)
573+
574+
>自上而下的上滤相当于**所有结点的深度之和**
575+
>
576+
>- 仅仅是叶子节点，就有近 n/2 个，而且每一个叶子节点的深度都是 O(logn) 级别的
577+
>- 因此，在叶子节点这一块，就达到了 O(nlogn) 级别
578+
>- O(nlogn) 的时间复杂度足以利用排序算法对所有节点进行全排序
579+
>
580+
>自下而上的下滤相当于**所有结点的高度之和**，时间复杂度推导过程如下
581+
>
582+
>![image-20230611133535363](https://cdn.fengxianhub.top/resources-master/202306111335493.png)
583+
>
584+
>其中第三步，中括号里面的其实就是一个等差数列和一个等比数列的乘积求通项公式的问题，可以使用`错位相减法`
585+
>
586+
>![image-20230611134351077](https://cdn.fengxianhub.top/resources-master/202306111343232.png)
438587
439588
## 附录：源码地址
440589

‎GoLang/golang最佳实践.md‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -106,7 +106,11 @@ func main() {
106106

107107
### 1.2 最佳实践
108108

109-
![img](https://cdn.fengxianhub.top/resources-master/202303310041136.avif)
109+
![img](https://cdn.fengxianhub.top/resources-master/202305042113604.avif)
110+
111+
112+
113+
![image-20230504211407049](https://cdn.fengxianhub.top/resources-master/202305042114298.png)
110114

111115
## 2. 测试最佳实践
112116

‎README.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -118,6 +118,10 @@
118118

119119
[集合set](/AlgorithmAndDataStructure/9-集合set.md)
120120

121+
**堆**
122+
123+
[二叉堆](/AlgorithmAndDataStructure/13-二叉堆.md)
124+
121125
## 🎈 大数据
122126

123127
[MapReduce基本使用](/大数据/hadoop/2-MapReduce/5-MapReduce学习.md) | [MapReduce原理剖析](/大数据/hadoop/2-MapReduce/6-MapReduce原理剖析.md) | [yarn学习](/大数据/hadoop/3-yarn/yarn学习.md)

‎SpringCloud/.DS_Store‎

-10 KB
Binary file not shown.

0 commit comments

Comments
 (0)