We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
1 parent 6e7dea8 commit ccb8652Copy full SHA for ccb8652
1 file changed
Week01/NOTE.md
@@ -1,19 +1,21 @@
1
-#第一周学习笔记
+# 第一周学习笔记
2
3
-##PriorityQueue源码分析
+## PriorityQueue源码分析
4
5
-###父类与接口
+### 父类与接口
6
PriorityQueue类(下称PQ)继承了AbstractQueue这一抽象类,因而具有Queue的所有方法;同时它也实现了Serializable这一接口,
7
因而PQ对象可以被表示为字节序列存储或传输。
8
9
-###底层逻辑结构与构造函数
+### 底层逻辑结构与构造函数
10
PQ的逻辑结构是一个通过数组实现的完全二叉树/堆。默认情况下PQ实现最小堆,但是可以通过传入一个comparator来实现自定义顺序存储。
11
找节点的父节点和子节点可以通过以下索引:
12
+```
13
leftChild = 2 * index + 1;
14
rightChild = 2 * index + 2;
15
parent = (index - 1) / 2;
16
17
-###时间复杂度
18
+### 时间复杂度
19
添加和删除由于都需要在操作后调整二叉树中元素的排列来重新达到有序的状态,时间复杂度均为O(nlogn)(此为最坏情况下的时间复杂度,
20
即插入的元素要从叶子节点sift up到根节点;或删除根节点后每一层的节点都需要sift up)。PQ的插入的平均时间复杂度也可以理解为
-O(1),因为只需要在堆的最后插入。
21
+O(1),因为只需要在堆的最后插入。
0 commit comments