数据结构 第六章(堆).ppt

1 堆 2 优先队列 问题的提出 日常工作安排计算机操作系统任务调度最大优先队列 性质 被删除的是优先级最高的元素任何时刻可插入任意优先级的元素最小优先队列 3 假设队列有n个元素 最大优先队列的存储结构 无序线性表顺序映射 插入操作很容易在表的尾端完成 其时间为O 1 删除操作需要查找优先级最高的元素并删除之 需要O n 时间链表结构 插入操作可在表的前端完成 其时间为O 1 删除操作的时间仍然为O n 有序线性表元素按优先级非递增次序排列 每次删除操作的时间为O 1 但每次插入操作的时间为O n 4 有没有其他更好的方式 树 为什么 O logmn 定义 最大树是一棵树 其中每个结点的key值不小于该结点子女 如果存在的话 的key值最大堆既是一棵完全二叉树 又是一棵最大树 5 最大堆的例子 6 最大堆的基本操作 1 创建空堆 2 将新元素插入堆中 3 从堆中删除key值最大的元素 7 最大堆的ADT定义如下 templateclassMaxHeap publicMaxPQ 对象 由n 0个元素构成的完全二叉树和最大树public MaxHeap intsz DefaultSize 创建空堆BooleanIsFull 判断堆中元素个数是否达到最大容量voidInsert Element 8 由于最大堆是一棵完全二叉树 所以可用数组heap表示 private Element heap intn 最大堆的当前元素个数intMaxSize 堆中可容纳元素的最大个数MaxHeap的构造函数如程序如下 MaxHeap MaxHeap intsz DefaultSize MaxSize sz n 0 heap newElement MaxSize 1 heap 0 不用 9 插入操作 最大堆的结点个数为n 插入一个新元素时为了保持完全二叉树性质 新增结点的编号应为i n 1为了保持最大树性质 还需要比较结点i和其双亲的key值如果结点i的key值大于其双亲的key值将结点i中的元素与其双亲的元素对换令结点i的双亲成为新的结点i 继续向上比较直到结点i的key值不大于其双亲的key值或i到达根结点为止 10 前述插入过程如下所示 11 函数Insert实现了最大堆插入操作 templatevoidMaxHeap Insert constElement 12 分析 插入过程从完全二叉树的叶结点开始 并向上移动 最坏情况下到根为止在此路径上每一个结点的处理时间是O 1 n个结点的完全二叉树的高度为 log2 n 1 插入函数的for循环最多迭代O logn 次插入函数的时间复杂性是O logn 13 删除操作 从最大堆中删除一个元素时 该元素必定在 根结点 结点1 中为了保持完全二叉树性质将结点n中的元素暂时存放在结点i 1中 最大堆的元素个数变为n 1 为了保持最大树性质比较结点i和其较大子女的key值若结点i的key值小于其较大子女的key值将结点i中的元素与其较大子女的元素对换令结点i的较大子女成为新的结点i 继续向下比较直到结点i的key值不小于其较大子女的key值或i到达叶结点为止 14 删除过程如下所示 15 最大堆删除操作 templateElement MaxHeap DeleteMax Element 16 分析 删除过程从完全二叉树的根结点开始 并向下移动 最坏情况下到叶为止在此路径上每一个结