DSA第5章堆和优先权队列.ppt

5 6堆和优先权队列 优先权队列中的元素 按其优先级的高低而不是按元素进入队列的次序 来确定出队列的次序 堆是一种很有用的数据结构 它可以用于高效地实现优先权队列 课堂提要第5章树5 1树的基本概念5 2二叉树5 3二叉树的遍历5 5树和森林5 6堆和优先权队列5 7哈夫曼树和哈夫曼编码 5 6 1堆 1 堆的定义 1 一个大小为n的堆 heap 是一棵包含n个结点的完全二叉树 该树中每个结点的关键字值大于等于双亲结点的关键字值 这样定义的堆称为最小堆 MinHeap 例如 右图的完全二叉树是最小堆 2 堆又可以定义为 堆是n个元素的序列 k0 k1 kn 1 当且仅当满足ki k2i 1且ki k2i 2 i 0 1 2 n 2 2 时称为堆 最小堆 例如 序列 23 53 34 65 83 74 是最小堆 2 堆的顺序存储表示堆的顺序表示是完全二叉树的顺序表示 3 向下调整和建堆运算 1 函数voidAdjustDown Tkeap intr intj 设序列以顺序方式保存在一维数组heap 中 数组元素具有可比较大小的类型 假定从数组中r 1到j 这j r个位置上的元素已满足ki k2i 1且ki k2i 2 i 0 1 2 n 2 2 条件 现向下调整第r位置上的元素 如果kr大于k2r 1和k2r 2 中的较小的元素 则将kr与该较小元素交换 继续这样的过程 直到不再需要调整 或到达堆底为止 templatevoidAdjustDown Theap intr intj intchild Ttemp heap r child 2 r 1 child是r的左孩子while childheap child 1 child if temp heap child break heap child 1 2 heap child child 2 child 1 heap child 1 2 temp 2 建堆运算它通过从第 n 2 位置开始 直到第一个元素 重复调用AdjustDown函数实现之 templatevoidMinHeap Theap intn for inti n 2 2 i 1 i AdjustDown heap i n 1 例 74 71 例 初始序列 5 6 2优先权队列 1 优先权队列优先权队列不同于先进先出 FIFO 队列 优先权队列中的元素 按其优先级的高低而不是按元素进入队列的次序 来确定出队列的次序 最小值为最高优先权 从优先权队列中删除最高优先权元素来实现优先操作 2 优先权队列的C 类Insert 将一个新元素插入优先权队列 Delete 从队列中取出具有最高优先级的元素 并从队列中删除之 3 优先权队列ADTADTPrioQueue 数据 n 0个元素的最小堆 运算 Create 建立一个空队列 Destroy 撤销一个队列 IsEmpty 若队列空 返回true 否则返回false IsFull 若队列满 返回true 否则返回false Append x 元素值为x的新元素插入队列 Serve x 在x中返回具有最高优先权的元素值 并从优先队列中删除该元素 程序5 12优先权队列的C 类templateclassPriorityQueue public PriorityQueue intmSize 20 PriorityQueue delete q voidAppend constT 优先权队列的构造函数和析构函数templatePriorityQueue PriorityQueue intmQSize maxSize mSize n 0 q newT maxSize PriorityQueue delete q 4 实现优先权队列AdjustDown和AdjustUp函数templatevoidAdjustDown Theap intr intj intchild Ttemp heap r child 2 r 1 child是r的左孩子while childheap child 1 child if temp heap child break heap child 1 2 heap child child 2 child 1 heap child 1 2 temp AdjustUp函数AdjustUp intj 设数组中0到j 1 这j个位置上的元素已满足ki k2i 1且ki k2i 2 i 0 1 2 n 2 2 条件 运行AdjustUp intj 将使得增加一个元素q j 这0 j个元素也满足堆的特性 AdjustUp函数templatevoidPriorityQueue AdjustUp intj inti j Ttemp q i while i 0 5 Append和Serve函数templatevoidPriorityQueue Append constT templatevoidPriorityQueue Serve T 设从空队列开始 依此向队列中插入元素 71 74 2 72 54 93 52 28 则每次插入后队列的状态如下表 从队列中删除最高优先权的元素2以后 队列中剩余元素排列如下 28 54 52 74 72 93 71 6 Append和Serve函数的时间容易分析优先权队列的插入和删除运算的时间复杂度 由于具有n