《牛小飞《数据结构》6优先队列.ppt》由会员分享，可在线阅读，更多相关《牛小飞《数据结构》6优先队列.ppt（24页珍藏版）》请在三一文库上搜索。
1、优先队列（堆） npriority queue n应用于操作系统的进程调度策略中 戌 猴 乏 良 待 舀 漂 梆 茄 谁 运 怒 胞 眨 钻 惧 蓬 你 假 香 湘 郸 年 俞 灵 以 雇 兔 腑 逊 慈 蓟 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 优先队列的基本模型 优先队列的实现思考 二叉堆 优先队列的应用 小结 优先队列（堆） 犬 喷 删 琵 威 颈 继 啥 补 堑 钻 忙 抄 貌 斡 锹 榴 侣 汞 鲍 跪 懈 粗 茬 秘 否 穴 缄 饰 恃 辛 赋 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6
2、优 先 队 列 优先队列的基本模型 优先队列 插入删除最小者 至少允许两种操作 ： insert deleteMin 等价于enqueue(入队) 是dequeue(出队)在优先队列中的等价 操作 俐 吞 昂 遵 竿 转 岸 昭 虫 吮 惧 怕 胚 嚏 醚 货 授 循 沿 偷 呛 闪 创 仙 暖 俩 嗓 堰 屡 粤 品 楞 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 优先队列实现思考 n链表：在表头执行插入操作O(1)，遍历该链表实 现删除最小元素O(n)。 n二叉查找树：deleteMin操作会损害树的平衡， 使得右子树加重。另外，二叉平衡
3、树支持更多 的但在优先队列中不需要的操作。 n二叉堆 阀 僚 宽 宋 资 签 床 沽 雍 咐 炒 痕 媳 适 势 事 养 钉 闻 卞 满 潮 络 坪 底 良 暴 升 蓄 瘸 捣 匈 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 二叉堆(binary heap) 堆的定义 二叉堆的性质：结构性质、堆序性质 二叉堆的操作：insert、deleteMin、buildHeap 二叉堆的应用：选择问题、事件模拟 卸 贡 暗 切 瓜 椰 川 筏 绕 吉 致 借 疾 给 橡 嵌 迪 径 呐 瑚 佐 灿 瓜 益 芍 擎 浙 商 游 绎 稗 团 牛 小 飞 数
4、 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 堆的定义 堆是满足下列性质的数列r1, r2, ，rn： 或(小顶堆)(大顶堆) 若将此序列所存储的一维数组R1n看做是一棵完全二 叉树的存储结构，则堆实质上是满足如下性质的完全二 叉树： 树中任一非叶结点的关键字均不大于(或不小于)其左 右孩子(若存在)结点的关键字。 榆 棕 铁 诺 的 础 浑 澎 纪 淮 厚 簧 氧 舰 娜 岳 膏 韶 母 扳 泵 钦 溶 丢 支 囊 疽 单 驹 晤 妊 体 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 堆的定义 小顶堆： 根
5、结点(亦称为堆顶)的关键字是堆里所有结点关键字 中最小者的堆称为小顶堆。 大顶堆： 根结点(亦称为堆顶)的关键字是堆里所有结点关键字 中最大者，称为大顶堆。 注意： 堆中任一子树亦是堆。 以上讨论的堆实际上是二叉堆(Binary Heap)，类 似地可定义k叉堆。 玛 馅 而 沪 霖 遏 哄 训 投 菜 优 轴 咆 果 贸 惨 蜀 搭 颜 眨 咸 酬 靖 羡 陶 称 赂 学 蝎 舱 司 歉 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 堆的定义 （13，38，27，50，76，65， 49，97） 13 3827 507665 49 97 （9
6、6，83，27，38，11，9） 小顶堆 96 8327 38119 大顶堆 能 盖 取 堪 唬 适 疾 冀 雄 锅 脆 踩 保 板 媚 教 语 哄 懊 颁 辐 慈 桥 污 翔 艇 厕 叼 旗 矩 宗 缩 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 二叉堆的结构性质 n二叉堆是一棵完全二叉树。所以， 可以用数组来表示。 A B C DEFG H IJ A B C D E F G H IJ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 n 对于数组中任一位置i上的元素 ， 其左孩子在位置2i上，右孩子在 左孩子后的位置(2i+
7、1)上。它的 父节点在i/2的位置上。 图中二叉堆大小的限界是13个元素。 顺 仆 肇 皇 纫 捅 戚 演 号 斟 苫 慷 饲 兜 着 鸵 旱 湍 鸦 坛 媒 猎 渣 击 宙 假 铁 呵 欣 涎 力 链 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 n在一个二叉堆中，对于每一个节点X，X的父亲中的关键字 小于（或等于）X中的关键字，根节点除外。 二叉堆的堆序性质 13 21 16 631 1968 65 2632 13 21 16 2431 1968 65 2632 二叉堆 非二叉堆 根据二叉堆的堆序性质 最小元总可以在根处找到 系 岳 蕴 旋
8、 随 估 佯 间 捶 汗 超 薪 挚 葡 貌 紊 曳 吾 丙 靶 绽 札 眺 躯 哀 砍 喜 掂 累 咀 泳 孟 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 n所有的操作都要保证堆序性质。 二叉堆的操作insert 插入操作的基本思想： 创建一个空穴，再将空穴上冒，这种 策略叫上滤(percolate up)。 朱 秘 耻 石 圭 界 奉 扦 挖 蒙 现 蛇 川 喝 侨 熔 疑 蚌 笼 夷 蓝 芝 夷 米 笨 押 薛 似 额 芒 痉 祈 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 二叉堆的操
9、作insert 13 21 16 2431 1968 65 2632 尝试插入14 13 21 16 2431 1968 65 2632 31 21 14 典 娱 羞 辱 瞳 爸 蓉 绣 氢 亢 橇 想 挖 挖 灭 鞍 石 援 勉 文 抬 配 杯 献 扮 类 壹 戈 元 贝 轧 乎 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 public void insert(AnyType x) if(currentSize=array.length-1) enlargeArray(array.length*2+1); int hole=+current
10、Size; for(;hole1 i-) percolateDown(i); 女 棕 身 涕 柒 杉 狼 傲 畏 炔 晌 泣 条 豪 童 浮 欢 乃 饥 扦 辗 呀 嗜 乒 瓶 叙 纂 宝 脾 早 婆 比 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 优先队列的应用选择问题 输入N个元素及一个整数k，这N个元 素的集可以是全序集。 该选择问题是要找出第k个最大元素。 当k=N时，算法称为堆排序。 密 氨 又 辨 勺 呵 晒 唤 肌 稳 矫 笆 匪 踊 达 糜 溉 啸 榔 尽 哗 菲 禽 谰 腾 猎 哨 超 戎 浊 髓 身 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列 小结和作业 1.基本模型 3.二叉堆 2.实现思考 1堆的定义 3二叉堆的操作 插入 删除 创建堆 2堆的性质 优先队列 作业：6.2、6.3 充 范 凉 喻 社 蹈 钝 矣 敝 菩 励 再 结 溜 厉 家 屡 简 帘 姨 绦 则 吗 筑 怂 楷 番 堪 匈 澡 笑 匿 牛 小 飞 数 据 结 构 6 优 先 队 列 牛 小 飞 数 据 结 构 6 优 先 队 列