第八章 优先队列和堆
1 子节点都小于父节点
2 医院看病 优先级 , 做手术 / 普通感冒
3 和普通队列主要区别在出队上
4 优先队列关键词 动态
5 队列中的元素不断变化 , 不能每次都根据优先级排序
6 游戏 AI 自动攻击范围的例子 优先级: 最近/最强悍/最弱的敌人
7 会有新的敌人加入 : 动态
8 接口和普通队列一致
9 优先队列有多种实现
10 普通线性结构实现 enqueue O 1 , 出队 O n , 取出最大元素
11 顺序线性结构 enqueue O n dequeue O 1
12 这不就是类似实现栈的 max , min O1 复杂度方法吗
13 堆实现优先队列 出入都是 logn 最差情况的复杂度
14 n 和 logn 的差距
15 logn的复杂度 基本和树有关
16 比如合并排序快速排序 , 其实形成了一科隐型的递归树
17 堆也是树结构
18 堆也有多种实现
19 二叉树实现的二叉堆 , 完全二叉树
20 直观理解 , 一层一层顺序放直到放完为止
21 最大堆 , 知识点 1
22 大小是相对的 , 什么是大什么是小是自己定义的
23 堆的定义 : 是完全二叉树 和 知识点 1
24 用数组表示完全二叉树
25 parent = i/2
26 left child = 2i
27 right child=2i+1
28 数学归纳法证明上面 3 个知识点
29 从索引 0 开始
30 parent = (i-1)/2
31 left = 2i+1
32 right=2i+2
33 用之前实现的 Array 类组合实现
34 记得改为泛型 Comparable
35 先写基本方法 size isempty 初始化容量 parent left right child
36 添加元素 在最后一层加 , 然后 shift up (依次和父亲节点比较) , 维持堆的性质
37 定义 add 用户接口 , 和 shiftup 内部接口 : 从 k索引开始上浮
38 给 array 类新增 swap 用户接口
39 shiftup 很简洁
40 extractMax
41 相当于有两个子堆 , 把最后一个元素放到堆顶 , 然后 shiftdown
42 shiftdown 和子节点比较 , 和较大的那个交换 , 直到没有子节点大于他
43 可以感觉到如果元素动态变化(一直在插入取出)的话 , 取出最值元素的效率很高 , 和树高度正相关
44 边界判断 : 左孩子没越界 , if 右孩子没越界 , 取出最大的 , 如果小于 , 则停止 , 否则 swap 后继续 shiftdown
45 如何用堆的设计思想进行原地排序
46 add 和 extractmax 都是 logn 和树高度相关
47 replace 操作 , 取出最大 , 然后放入新元素 = extractMax + add 2logn
48 replace 优化 : 替换堆顶元素后 shift down
49
50 heapify 操作 : 将数组整理成堆的形状
51 第一种方法 , 数组中每个元素 add 入堆中
52 第二种方法 , 原地操作 , 数组已经满足完全二叉树的性质
53 只需要再满足第二个性质 , 父节点大于子节点就行了
54 叶子节点都可以看做是满足性质的子堆
55 把上层的节点 shift down 让每个子堆都满足性质
56 最后一个非叶子节点 = 最后一个叶子节点的 parent
57
58 heapify 的动画演示
59
60
61
62 除了堆 , 还有什么实现优先队列的方法
63 topk 问题 在 N 个元素选出 M 个元素 , M 远远小于 N
64 使用一个优先队列维护当前扫描到的前 M 大元素
65 由于每次需要替换掉的是队列中最小的元素 , 所以需要使用最小堆
66 大小是相对的 , 也可以用最大堆来实现 , 只要定义越小的元素优先级越高
67 leetcode 347 top k frequent
68 定义优先级
69 nlogk
70 java自带优先队列类的使用 , 和优先级定义的接口覆写 (比较器)
71 java的匿名类
72 匿名类再精简成lambda表达式
73 leetcode 其他堆的问题 , 安排好时间 , 不用全做
74 除了上面讲的二叉堆 , 还有N叉堆 , 层数更低
75 但是shift up , shift down的操作代价变高了
76 上面实现的堆看不到中间的元素
77 索引堆可以做到 , 应用广泛 , 高级数据结构 在另一个门修炼课里有讲
78 是后面图轮 和 最短路径算法学习的一个prerequisities
79 索引堆 当做拓展学习就好了
80
81 二分搜索树的前序遍历和层序遍历 , 一个是用栈 , 一个是用队列 , 其实只是数据的入队出队方式不同
82 在深度实战算法中 , 迷宫那一章 , DFS和BFS的内在联系 , 逻辑是一致的 , 本质的区别是使用了什么样的数据结构
83 随机队列
