优先队列及其应用.ppt

优先队列及其应用 雅礼朱全民 优先队列的基本概念 队列 FIFO 按元素进入队列的次序 优先队列 PriorityQueue 出队列的顺序由元素的优先级决定 如 医院中的急诊处理 操作系统中使用优先队列进行作业调度 事件驱动模拟处理 优先队列的基本操作 ADTMaxPriorityQueue 实例有限的元素集合 每个元素都有一个优先权操作Create 创建一个空的优先队列Size 返回队列中的元素数目Max 返回具有最大优先权的元素Insert x 将x插入队列DeleteMax x 从队列中给删除具有最大优先权的元素 并将该元素返回至x 假设我们对机器服务进行收费 每个用户每次使用机器所付费用都是相同的 但每个用户所需要服务时间都不同 为获得最大利润 假设只要有用户机器就不会空闲 我们可以把等待使用该机器的用户组织成一个最小优先队列 优先权即为用户所需服务时间 当一个新的用户需要使用机器时 将他 她的请求加入优先队列 一旦机器可用 则为需要最少服务时间 即具有最高优先权 的用户提供服务 如果每个用户所需时间相同 但用户愿意支付的费用不同 则可以用支付费用作为优先权 一旦机器可用 所交费用最多的用户可最先得到服务 这时就要选择最大优先队列 引例1 机器服务收费 引例2工厂仿真 对其事件队列所执行的操作查找最小完成时间的机器改变机器的完成时间构造构造一个最小优先队列 队列中的元素即为机器 元素的优先权为该机器的完成时间 当机器可用 选择优先级最大的任务执行 任务队列操作 新任务到达 插入最大优先队列一旦机器可以开始运行一个新任务 将具有最大优先权的任务从该机器的队列中删除 并开始执行它 优先队列的线性表实现 优先队列的另一种实现方式 堆 Heap 无序顺序表插入在表的末尾 1 删除时先查找优先权最大的元素 n 无序链表插入在链头 1 删除时先查找优先权最大的元素 n 有序线性表插入时间 n 删除时间 1 一个基本问题 写一种数据结构 完成以下3种操作 操作的总次数不超过100000 1 插入一个数2 询问最小值3 删除最小值要求是这3种操作都要快 输入输出 输入每行一次操作 有如下三种 1x 表示插入X这个数2 表示询问当前最小值3 表示删除最小值输出对于每个询问最小值操作 输出一行 每行仅一个数 表示当前的最小值 样例 输入 9 9次操作120213011023232 输出 20102030 用线性表作为数据结构 无序表 插入操作O 1 询问最小值O n 删除最小值O n 有序表 插入操作O n 询问最小值O 1 删除最小值O 1 堆的定义 如果将此数据元素序列用一维数组存储 并将此数组对应一棵完全二叉树 则堆的含义可以理解为 在完全二叉树中任何非终端节点的值均不大于 或小于 其左 右孩子节点的值 设有n个数据元素的值为 k1 k2 kn 如果它们满足以下的关系 ki k2i且ki k2i 1 或ki k2i且ki k2i 1 i 1 n 2 则称之为堆 Heap 堆 Heap 最小堆 MinHeap 最大堆 MaxHeap 最小 大 堆 位于堆顶 即完全二叉树的根节点位置 的节点的值是整个序列中最小 大 的 ki k2i且ki k2i 1 ki k2i且ki k2i 1 在堆中插入元素x 首先将元素x放到堆中的最后一个位置 即最底层最右边的位置 然后不断地把x往上调整 直到x调不动为止 即大于它现在的父亲 或者x处于根结点 定义一个堆 Varst array 1 maxn oflongint 存储堆n longint 堆中元素个数 插入 实际上是不断向上调整的过程 PROCup k longint 把第k个结点上调 beginwhilek 1dobegini kdiv2 i是k的父亲 ifst i st k thenbeginswap i k k i 交换结点i和k endelseexit end end 在堆中删除任意一个元素 这里说指的删除任意一个元素 是指在当前堆中位置为w的元素 过程如下 首先把位置w的元素和最后一个位置的元素交换 然后删去最后一个位置 这样w上的元素就被删除了 接着把位置w上的新元素不断下调 直到满足堆的性质 删除 实际上是不断向下调整的过程 PROCdown k longint 把第k个结点往下调 beginwhilek k ndobegini min 2k 2k 1 如果2k 1不存在直接返回k k否则返回2个中间的值较小的元素 ifst i st k thenbeginswap i k k i endelseexitend end 堆的构造就是不断插入到堆的过程 堆的插入 删除 PROCadd x longint 添加一个值为x的元素 begininc n st n x up n end PROCdel x longint 删除一个值为x的元素 begina n a x down x end d 堆 多叉堆优先队列无法全部装入内存在实际应用中 4 堆可胜过二叉堆 左高树 或左偏树 高度与宽度优先的最大及最小左高树堆 隐式 implicit 数据结构没有明确的指针 没有存储结构信息空间利用率最高不适用所有优先队列应用 合并长度不等的优先队列左高树 leftisttree 适合此类应用 扩充二叉树 外部节点 内部节点 函数s x 的定义 s x x到其子树外部节点路径长度最短值外部节点 s x 0内部节点 s x min s L s R 1L R x的左右孩子 左高树定义 定义 高度优先左高树 当且仅当一棵二叉树的任一内部节点 其左孩子的s值大于等于右孩子的s值 该二叉树为高度优先左高树 height biasedleftisttree HBLT 定理 定理 令x为一个HBLT的内部节点 则以x为根的子树的节点数目至少为2s x 1 若子树x有m个节点 s x 最多为log2 m 1 通过最右路径 即 此路径是从x开始沿右孩子移动 从x到达外部节点的路径长度为s x 证明 由s x 定义 从x向下的s x 1层内没有外部节点 否则s x 将更小 子树第一层只有x 下一层有两个 第s x 1层有个2s x 1 节点数目至少为由1 可得2 根据s的定义 及HBLT一个节点的左孩子的s值总是大于等于其右孩子的s值 可以推得3 成立 最大 小 HBLT 定义 最大 小 HBLT 即同时又是最大 小 树的HBLT 重量 w x 以x为根的子树的内部节点数目外部节点 w x 0内部节点 w x w L w R 1 重量优先左高树 定义 重量优先左高树 当且仅当一棵二叉树的任一内部节点 其左孩子的w值大于等于右孩子的w值 该二叉树为重量优先左高树 weight biasedleftisttree WBLT 最大 小 WBLT 即同时又是最大 小 树的WBLT HBLT和WBLT的操作 查找 插入 删除与堆一样初始化也可在线性时间内完成两个优先队列合并 对数时间 这是堆达不到的 最大HBLT的插入 删除操作 插入操作可借助合并操作元素x插入到名为H的最大HBLT 构造只有一个元素x的最大HBLTH H 与H合并删除操作也可借助合并操作删除根节点 两个子树L R均为最大HBLT合并L R 最大HBLT的合并操作 遍历右路径 O logn 递归 合并A B若一个为空 则另一个为合并结果若都不空比较两个根节点 较大者为新的根假定A较大 左子树为L 右子树为R递归方法将R与B合并为C最终合并结果 A的根为根 L C的s值较大者为左子树 另一个为右子树 插入操作实例1 插入操作实例2 A B 插入操作实例3 A B 插入操作实例4 A B 初始化最大HBLT n个元素依次插入空HBLT O nlogn 线性时间算法构造n个单元素的HBLT FIFO队列删除队列前两个HBLT 合并 加入队尾重复 直至只剩一个HBLT 初始化实例 希望构造具有五个元素 7 1 9 11 2的一棵最大HBLT 如下图 7 1合并成为a 9 11合并成为b 2和a 合并成为c 最后b 和c 合并成为d 复杂性分析 初始化的复杂性n是2的幂 合并n 2对一个元素的HBLT 合并n 4对二个元素的HBLT 合并两棵2i个元素的HBLT O i 1 总时间复杂性 斜堆 skewheap 斜堆可递归的定义如下 只有一个元素的堆是斜堆 两个斜堆通过斜堆的合并操作 得到的结果仍是斜堆与左高树类似 但无 左高 这一限制各种操作与左高树类似 也是以合并为基础但递归合并过程中 左右孩子的交换不是以达到 左高 为目的 而是无条件的 只有最后 右 节点例外 递归停止 斜堆的合并操作 我们可以用左高树的合并算法实现两个斜堆的合并 除此之外 还有一种非递归的算法 分割每个堆 方法是从根节点开始 右子树与根节点分离 然后右子树以同样的方式分割 最后得到一个树的集合 集合中的树的特点是 其根节点只有左子树或者没有子树 对集合中的树 按照根节点的值从小到大排序 从右到左 不断地合并最后两个子树 直到只剩下一棵树 合并方法是 如果倒数第二棵树有左子树 那么把左子树变为右子树 把最后一棵树作为倒数第二棵树的左子树 斜堆合并示例 非递归实现 斜堆合并示例 递归实现 斜堆的摊还分析 证明斜堆合并的摊还时间为O logN 定义 一个节点p 若其右子树的后裔数至少是p的后裔数的一般 则称p是重节点 否则称为轻节点位势的选取 右路径上重节点的数目 斜堆的摊还分析 证明 令H1和H2为两个斜堆 节点数为N1和N2 右路径上轻重节点数目分别为l1和h1 l2和h2若合并代价定义为右路径上节点总数 则代价为l1 h1 l2 h2合并操作的重要特性 右路径上的重节点肯定变为轻节点 而轻节点可能不变 也可能变为重节点 考虑最坏情况 当然是所有轻节点均变为重节点则位势 重节点数 的变化为l1 l2 h1 h2平均摊还时间 代价 位势变化 2 l1 l2 现在只需证明l1 l2 O logN 而l1和l2是原右路径上的轻节点数目 而轻节点左子树重 右子树轻 因此l1 l2至多为logN1 logN2 即O logN 而初始位势为0 始终非负 命题得证 二项队列 binomialqueue 二项树 binomialtree 堆序树 的森林二项树的结构 递归构造高度为0 B0 单节点树高度为k Bk 由一棵二项树Bk 1附接到另一棵Bk 1的根上而得 二项树例 二项树特性 Bk的根节点的子树为B0 B1 Bk 1高度为k的二项树恰有2k个节点d层的节点数目为二项系数令二项树为堆序 且每个高度仅有一棵二项树 则可用二项队列惟一表示任意大小的优先队列 二项队列表示优先队列例 优先队列大小为13 1101 显然每个1对应一棵二项树 B3 B2 B06个元素的优先队列表示为下图二项队列 取最小元操作 取所有二项树根节点中最小者O logN 在其他操作过程中记录最小根节点 则可提高到O 1 合并操作 二进制数相加6个元素和12个元素的二项队列合并110 1100 由低至高逐位相加0 0 0 两个队列均无B0 合并后自然也没有1 0 1 一个队列有B1 另一个没有 合并后队列中的B1自然来自前者1 1 10 将两个B2中根较大者附接到较小者 得到一个B3 进位 结果中无B20 1 1 10 类似步骤三 得到一个B4 结果中无B310010 结果二项队列包含一个B1和一个B4 合并操作例 13放入结果队列 两个B1合并为B2 最终结果 三个B2 两个合并变为B3 一个保留 O logN 插入操作 最坏情况O logN 精确 最低位起 第一个0在第i位 则运行时间正比于i 1每位为0的概率为1 2 平均情况O 1 例 将1至7插入空二项队列 DeleteMin 先找到具有最小根的二项树Bk O logN 将Bk从二项队列中去掉 得到新的二项队列H 将Bk的根去掉 其子树构成二项队列H 将H 和H 合并即可 O logN DeleteMin例 显然应该删除B3的根12 DeleteMin例 续 H 和H 为 DeleteMin例 续 H 和H 合并后结果为 二项队列的实现 二叉树表示树较大的子树更靠前 左 摊还分析 amortizationanalysis一般的复杂性分析 算法运行一次所需要的时间算法如果运行不只一次呢 如果每次运行之间相互无关 同样OK但如果多次运行之间是相关的呢 考虑多次运行的总时间 再除以运行次数 得到一个 平均时间 注意区分平均情况时间复杂性很多算法 单独考虑一次运行 最坏情况很差 但摊还分析表明其连续运行性能很好 二项队列的创建 对空二项队列中进行N次插入操作每次操作 一个二进制数 1倒数第一个0在倒数第c位 花费时间c二进制数的变化 0 1 N 1 N第0 2 4 6 次操作 花费1第1 5 次操作 花费2 时间复杂性O N 创建操作的摊还分析 倒数第一个0在倒数第c位 花费时间c 效果是去掉了c 1棵树 增加一棵树 二项树的数目变化为2 c令Ci为第i次插入代价 Ti为第i次插入后树的数目 则T0 0 可得到公式Ci Ti Ti 1 2因此C1 T1 T0 2C2 T2 T1 2 CN TN TN 1 2消去得由于对任何N TN都是非负的 显然时间复杂性为O N 摊还分析 位势 potential 某一时刻的状态Tactual DPotential Tamortized类似分期付款平均每月应还X元前N个月应还N X元 但不必每月均还X元 有钱就多还点 没钱就少还点 保证总值即可上例的位势为二项树的棵数平均2个操作完成一次插入很多情况下1个操作即可 省下来的1个操作被 存入 位势 后面需多个操作时从位势 支取 位势的选取初始值为0 始终非负位势的变化应与算法代价相联系 应用1机器调度 问题描述一个机械厂 有m台相同的机器现有n个作业需要处理 作业i的处理时间ti 作业放入机器直到从机器上取下的时间调度 schedule 按作业在机器上的运行时间对作业进行分配 使得一台机器在同一时间内只能处理一个作业一个作业不能同时在两台机器上处理作业i一旦运行 则需要ti个时间单位0时刻所有机器均可用完成时间 完成所有作业的时间非抢先调度 作业调度例 七个作业所需时间 2 14 4 16 6 5 3 求完成时间最短的调度方案 NP 完全问题近似算法 近似最优解 最长处理时间优先调度策略 longestprocessingtimefirst LPT接近最优的完成时间 最优解的4 3 1 3m算法所有作业按处理时间递减排序每个作业分配给最先空闲的机器 LPT调度实例 上例排序 4 16 2 14 5 6 6 5 3 4 7 3 1 2 4 M1 16 2 M2 14 5 M3 6 6 M3 11 3 M3 15 7 M2 17 1 M3 17 LPT性能 定理9 2 Graham 令F I 为在m台机器上执行作业集合I的最佳调度完成时间 F I 为采用LPT调度策略所得到的调度完成时间 则 LPT算法的实现 利用堆将n个作业利用HeapSort按处理时间递增排序m台机器按可用时间维护一个最小堆 作业分配 应用2 哈夫曼树 给定m个实数w1 w2 wm m 2 要求一个具有m个外部节点的扩充二叉树 每个外部ki节点有一个wi与之对应 作为它的权 使得带权外部路径长度最小 其中li是从根到外部节点的路径长度 算法 1 构造m个只有1个节点的树2 找两个最小的权3 以这两个节点为左右儿子构造一个二叉树 并将该数的根节点权之为左右儿子权值之和4 继续第二步 直到剩下一棵树为止 应用3 任务 有n个任务 每个任务有一个截止完成的时间Ti和完成需要的时间Ci 现在你一个人希望从0时刻开始完成尽量多的任务 问最多能完成多少任务 分析 首先不妨将任务按照截止时间排序 这时候我们可以采用贪心方法 尽量选截止时间比较晚 同时需要时间比较少的任务完成是最好的 于是得出一个结论 假设最优方案的组成的任务集合是U 如果存在一个不属于U的任务j 对于某个属于 的 满足Tj Ti而且 j Ci 那么把 从 中删除 而把 替换过来 肯定仍然满足题目要求 也是一组最优方案 分析 考虑排序后前i个任务组成的最优方案集合是 i 下面看第i 1个任务 如果第i 1个任务直接加入后 依然满足题目要求 那么前i 1个任务最后方案集合就是Ui 1 Ui i 1 否则我们找到Ui中需要时间最长的任务K 如果Ck Ci 1那么根据定理1 将K i 1替换后肯定更优 于是得到了一个算法的基本流程 1 将任务按照Ti排序 2 从小到大枚举i 维护当前最优方案的集合U 每次将当前的任务I加入U后 如果不满足条件了 那么删去U中耗时最长的任务 3 输出最优方案即可 因此我们需要使用一种数据结构 它能快速删除耗时最长的任务 同时快速的插入一个新元素 显然 使用大根堆即能满足题目要求 应用4 juice Jonh正在研制一种有趣的 水杯 1 底面是WxH的相同小方格组成 3 W 300 3 H 300 2 每个小方格上放置一个底面是1x1的 高度是B 1 B 1 000 000 000 的水晶块 这些水晶块都粘贴在一块 之间不会漏水 John在制成之前 想知道他所要制的这种 水杯 能最多装多少水 juice 样例数据 4558775215717189699899 样例输出 12 解释 两个高度为1的和一个高度为2的可装水到高度为5 一个高度为6的可装水到高度为7 共装水 2 4 3 1 12 分析 木桶效应 盛水的多少 不在于木桶上那块最长的木板 而在于木桶上最短的那块木板 因此 我们从 边上 考虑 每次优先处理的是 最短的那块木板