数据结构与算法分析第六章 优先队列(堆).ppt

第六章 优先队列(堆) 本章纲要 1.优先队列模型 2.二叉堆 3.优先队列的应用 4.d-堆 5.左式堆 6.斜堆 7.二项队列 1.优先队列模型 队列 FIFO 排队等候买票 优先级 例如，救护车过红灯 对队列而言，队首元素先出队，暗含了队首优先级最高。 1.优先队列模型 优先队列 队列中元素具有不同的优先级，优先级高的元素先出队（deque） 遵守队列队首先出队的规则 因此，在优先队列中，优先级最高的元素应在队首。 入队（enque）?插入（insert） 出队（deque）?（deletemin） 1.优先队列模型 实现 链表 数组 二叉查找树 2.二叉堆 若有n个关键字的集合K={k1,k2, …,kn}将其所有元素按完全二叉树的顺序存贮方式存于一个一维数组中，并且满足以下条件，则该集合称为最小堆（或最大堆）。 ki≤k2i和ki≤k2i+1 或 ki≥k2i和ki≥k2i+1 ( 其中，i = 1,2, …?(n – 1) / 2? ) 2.二叉堆 高为h的完全二叉树有2h到2h+1-1个节点，完全二叉树的高为O(logN) 完全二叉树的数组存储 2.二叉堆 ADT 假设关键字越小，优先级越高 初始化 2.二叉堆 插入（insert）(上滤) 新元素插到堆的后面，这样可能破坏了堆序性。 为恢复堆序性，从插入元素双亲开始逐层向上筛选。 2.二叉堆 Deletemin 即删除堆顶元素，数组中1号位置元素 删除操作破坏了完全二叉树结构 下滤 见图6-9到6-11。 2.二叉堆 DecreaseKey 减少关键字的值?提高优先级 上滤 任务管理器中的进程管理 DecreaseKey 增大关键字的值?降低优先级 下滤 Delete 首先decreasekey，然后deletemin 进程被终止 2.二叉堆 Buildheap（构建堆） 1.自上而下构建 依次插入每个元素，总保证堆序性 2.自下而上构建 N个元素不考虑堆序性，直接存储到一个完全二叉树中； 从第N/2个元素到第一个元素依次使用下滤，就得到一个堆。 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆 2.二叉堆 自上而下构建堆时间复杂度 最大比较次数：log2+log3+……log(n-1)+logn 2.二叉堆 2.自下而上构建 2.二叉堆 2.自下而上构建 2.二叉堆 2.自下而上构建 2.二叉堆 2.自下而上构建 2.二叉堆 2.自下而上构建 2.二叉堆 2.自下而上构建 2.二叉堆 2.自下而上构建 时间复杂度分析 时间复杂度是所有节点高度之和 定理：包含2b+1-1个节点高为b的理想二叉树的节点的高度的和为2b+1-1-(b+1). 而2b=N2b+1， 所以时间复杂度为O(N) 3.优先队列的应用 第一章中的问题：从N个元素的集合中找出第k个最大的元素。 1.将N个元素读入数组，然后排序，返回第k个元素。 O(N2) 2.对前k个输入元素从大到小排序，后面的元素根据大小插入到合适位置，并删除第k+1个元素。所有元素插入完成后，第k个最大的元素就在第k个位置。 O(Nk) 当k=N/2，得到O(N2) 3.优先队列的应用 用优先队列解决 读入N个元素 构建堆 执行k次deletemin 最后一次就是所求。 读入k个元素 构建堆 插入新元素（必要时，删除最小元素） 根结点就是所求 4.d-堆 等同于一个完全d叉树 二叉堆相当于2-堆 一个3-堆示例 5.左式堆 零路径长（null path length，NPL）：任一节点X到一个没有两个儿子的节点的最短路径长。 5.左式堆 NPL(NULL)=-1 设X为任一节点 NPL(X) =1+min{ NPL(LeftChild(X))，NPL(RightChild(X)) } 若x度数为0或1： NPL(x) =0 若x度数为2： 按照上述计算式 5.左式堆 左偏性：对任一节点X，左儿子的零路径长大于等于右儿子的零路径长。 左式堆 同时满足堆序性和左偏性的二叉树 5.左式堆 左式堆中，根的零路径长对应的路径是最右边的路径（右子树的右子树…），简称右路径。 证明： 利用定义NPL(左子树)=NPL(右子树) 根的零路径长= NPL(右子树)+1 迭代… 故根的零路径长对应的是右路径 5.左式堆 5.左式堆 基本操作：合并 适合合并 简单易操作 合并： 互相递归与右子树合并 堆序性：大key节点与小key节点右子树合并 左偏性：不满足时，交换左右