第四章树与树的表示(四)规范.ppt

4.6 树的应用 4.6.1 堆(heap)及其操作 “堆(Heap)”正是考虑了适合于特权需要的数据结构，因此，堆也通常被称作为“优先队列”。 1.堆的定义和表示 优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。 问题：如何组织优先队列？ ? 一般的数组、链表？ ? 有序的数组或者链表？ ? 二叉搜索树？ AVL树？ 若采用数组或链表实现优先队列 ? 数组 : 插入 — 元素总是插入尾部 删除 — 查找最大（或最小）关键字 从数组中删去需要移动元素 ? 链表: 插入 — 元素总是插入链表的头部 删除 — 查找最大（或最小）关键字 删去结点 ? 有序数组: ~O(1) ~O( n ) ~O( n ) ~ O(1) ~ O( n ) ~ O( 1 ) 插入 — 找到合适的位置 移动元素并插入 删除 — 删去最后一个元素 ? 有序链表: 插入 — 找到合适的位置 插入元素 删除 — 删除最后元素 ~ O( n ) 或 O(log2 n ) ~ O( n ) ~ O( 1 ) ~ O( n ) ~ O( 1 ) ~ O( 1 ) ? 是否可以采用二叉树存储结构？ ? 二叉搜索树？ ? 如果采用二叉树结构，应更关注插入还是删除？ ? 树结点顺序怎么安排？ ? 树结构怎样？ ? ? 优先队列的完全二叉树表示 a b c h d i e f g a b c d e f g h i 0 1 2 3 4 5 6 7 8 9 10 11 ? 堆的两个特性 ?结构性：用数组表示的完全二叉树； ?有序性：任一结点的关键字是其子树所有结点的最大值(或最小值) “最大堆(MaxHeap)”,也称“大顶堆”：最大值 “最小堆(MinHeap)”,也称“小顶堆” ：最小值 【例】最大堆和最小堆 56 21 5 17 19 40 16 30 19 30 10 18 9 3 49 18 38 33 注意：从根结点到任意结点路径上结点序列的有序性！ 【例】不是堆 56 21 5 37 19 40 16 30 19 30 10 18 3 49 15 38 33 2.堆的抽象数据类型描述 类型名称：最大堆（MaxHeap） 数据对象集：完全二叉树，每个结点的元素值不小于其子结点的元素值 操作集：最大堆H∈MaxHeap，元素item ∈ ElementType，主要操作有： ?MaxHeap Create( int MaxSize )：创建一个空的最大堆。 ?Boolean IsFull( MaxHeap H )：判断最大堆H是否已满。 ?Insert( MaxHeap H, ElementType item )：将元素item插入最大堆H。 ?Boolean IsEmpty( MaxHeap H )：判断最大堆H是否为空。 ?ElementType DeleteMax( MaxHeap H )：返回H中最大元素(高优先级)。 { （1）最大堆的操作 ? 最大堆的创建 typedef struct HeapStruct *MaxHeap; struct HeapStruct { 把MaxData换成 小于堆中所有元素的 MinData，同样适用于 创建最小堆。 ElementType *Elements; /* 存储堆元素的数组 */ int Size; int Capacity; /* 堆的当前元素个数 */ /* 堆的最大容量 */ }; MaxHeap Create( int MaxSize ) /* 创建容量为MaxSize的空的最大堆 */ MaxHeap H = malloc( sizeof( struct HeapStruct ) ); H-Elements = malloc( (MaxSize+1) * sizeof(ElementType)); H-Size = 0; H-Capacity = MaxSize; H-Elements[0] = MaxData; /* 定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 */ return H; } 20 ? [2] 25 18 [4] [3] [5] [6] Case 1 : new_item = 20 20 31 Case 2 : new_item = 35 35