Skip to content

Commit ccb8652

Browse files
authored
Update NOTE.md
1 parent 6e7dea8 commit ccb8652

1 file changed

Lines changed: 8 additions & 6 deletions

File tree

Week01/NOTE.md

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,21 @@
1-
#第一周学习笔记
1+
# 第一周学习笔记
22

3-
##PriorityQueue源码分析
3+
## PriorityQueue源码分析
44

5-
###父类与接口
5+
### 父类与接口
66
PriorityQueue类(下称PQ)继承了AbstractQueue这一抽象类,因而具有Queue的所有方法;同时它也实现了Serializable这一接口,
77
因而PQ对象可以被表示为字节序列存储或传输。
88

9-
###底层逻辑结构与构造函数
9+
### 底层逻辑结构与构造函数
1010
PQ的逻辑结构是一个通过数组实现的完全二叉树/堆。默认情况下PQ实现最小堆,但是可以通过传入一个comparator来实现自定义顺序存储。
1111
找节点的父节点和子节点可以通过以下索引:
12+
```
1213
leftChild = 2 * index + 1;
1314
rightChild = 2 * index + 2;
1415
parent = (index - 1) / 2;
16+
```
1517

16-
###时间复杂度
18+
### 时间复杂度
1719
添加和删除由于都需要在操作后调整二叉树中元素的排列来重新达到有序的状态,时间复杂度均为O(nlogn)(此为最坏情况下的时间复杂度,
1820
即插入的元素要从叶子节点sift up到根节点;或删除根节点后每一层的节点都需要sift up)。PQ的插入的平均时间复杂度也可以理解为
19-
O(1),因为只需要在堆的最后插入。
21+
O(1),因为只需要在堆的最后插入。

0 commit comments

Comments
 (0)