第9章 优先队列(Priority Queues)

Presentation on theme: "第9章 优先队列(Priority Queues)"— Presentation transcript:

1 第9章 优先队列(Priority Queues)

2 本章内容 9.1 引言 9.2 线性表 9.3 堆 9.4 左高树 9.5 应用

3 Bird’s Eye View Unlike the queues, which are FIFO structures, the order of deletion from a priority queue is determined by the element priority (优先度）. Elements are deleted either in increasing or decreasing order of priority rather than in the order in which they arrived in the queue. A priority queue is efficiently implemented using the heap data structure, which is a complete binary tree that is most efficiently stored using the formula based representation.

4 9.1 引言 优先队列 优先队列（priority queue）是0个或多个元素的集合， 每个元素都有一个优先权或值。
9.1 引言 优先队列 优先队列（priority queue）是0个或多个元素的集合， 每个元素都有一个优先权或值。 对优先队列执行的操作有: 1)查找一个元素 2)插入一个新元素 3)删除一个元素

5 优先队列 两种优先队列: 最小优先队列（Min priority queue） 最大优先队列（Max priority queue）
优先权队列中的元素可以有相同的优先权。

6 最大优先权队列的抽象数据类型描述 抽象数据类型 MaxPriorityQueue{ 实例 有限的元素集合，每个元素都有一个优先权 操作
Create()：创建一个空的优先队列 Size()：返回队列中的元素数目 Max()：返回具有最大优先权的元素 Insert(x)：将x插入队列 DeleteMax(x)：从队列中删除具有最大优先权的元素，并将该元素返回至x } 最小优先权队列的抽象数据类型描述?

7 优先队列的描述 优先队列的描述 线性表 堆（Heaps） 左高树（Leftist trees）

8 9.2 线性表 采用无序线性表描述最大优先队列 采用有序线性表描述最大优先队列 公式化描述（利用公式Location(i)=i-1)
9.2 线性表 采用无序线性表描述最大优先队列 公式化描述（利用公式Location(i)=i-1) 插入：表的右端末尾执行，时间: (1) ; 删除:查找优先权最大的元素，时间: (n) ; 使用链表， 插入：在链头执行，时间: (1) ; 删除: (n) ; 采用有序线性表描述最大优先队列 公式化描述（利用公式Location(i)=i-1，元素按递增次序排列) 插入: O(n) ;删除: O(1) ; 使用链表（按递减次序排列）

9 9.3 堆(Heaps) 9.3.1 定义 定义[最大树（最小树）] 每个节点的值都大于（小于）或等于其所有子树中节点（如果有的话）值。
A max tree (min tree) is a tree in which the value in each node is greater (less) than or equal to those in its children (if any) 最大树或最小树不一定必须是二叉树。

10 例:最小树 2 4 9 3 8 7

11 例:最大树 9 4 8 2 7 3 1

12 最大树 最小树

13 The definition of Max(Min) Heap
A max heap (min heap) is a max (min) tree that is also a complete binary tree. 即若限定最大( 最小树）为2叉完全树，则称为堆。

14 定义[最大堆（最小堆）] ：最大（最小）的完全二叉树。

15 最小堆 2 4 6 7 9 3 8

16 最大堆 9 8 6 7 2 5 1

17 堆是完全二叉树，可用一维数组有效地描述堆.
9 8 6 7 2 5 1 ……

18 最大堆的插入 思想：先插入到最后一个位置，然后沿通向根的路径调整 9 8 6 7 2 5 1 新元素是5

19 9.3.2 最大堆的插入 9 8 6 7 2 5 1 20 新元素是20

20 9.3.2 最大堆的插入 9 8 6 7 2 5 1 20

21 9.3.2 最大堆的插入 9 6 7 2 5 1 8 20

22 9.3.2 最大堆的插入 6 7 2 5 1 8 9 20

23 9.3.2 最大堆的插入 插入的时间复杂性: 每一层的工作，耗时：(1)
实现插入策略的时间复杂性为：O(height) = O(log2n), （ n 是堆的大小）

24 9.3.3 最大堆的删除 思想:取走根的元素，然后把最后元素放到根，按最大树的性质向下调整 20 6 7 2 5 1 15 8 9

25 9.3.3 最大堆的删除 6 7 2 5 1 15 8 9 最大元素被删除以后

26 9.3.3 最大堆的删除 6 7 2 5 1 15 8 9 具有10个节点的堆. 在堆中重新插入8 .

27 9.3.3 最大堆的删除 6 7 2 5 1 15 9 8 需要进行调整（或重构）。左子树和右子树是最大堆

28 9.3.3 最大堆的删除 6 7 2 5 1 9 15 8

29 9.3.3 最大堆的删除 6 7 2 5 1 8 15 9

30 9.3.3 最大堆的删除 删除的时间复杂性: 删除的时间复杂性与插入的时间复杂性相同. 每一层的工作，耗时：(1)
实现删除策略的时间复杂性为：O(height) = O(log2n), （ n 是堆的大小）

31 最大堆的初始化 We can construct the initial nonempty heap by performing n insertions into an initial empty heap. The total time taken by n insertion is O(nlog2n). We may initialize the heap in O(n) time by a different strategy. The main idea is that Let the array of n element be a complete binary tree, then convert it into a max-heap. Beginning at the element at i= n/2 ,adjust the subtree rooted i into a heap. Following the adjust, we examine the subtrees rooted at i-1,i-2,…,1

32 9.3.4 最大堆的初始化 a = [20,12,35,15,10,80,30,17,2,1] n=10, n/2=5 [1] [3]
最大堆的初始化 a = [20,12,35,15,10,80,30,17,2,1] n=10, n/2=5 [1] 20 [3] [2] 12 35 [5] [7] [4] [6] 15 10 80 30 i 17 2 1 [9] [8] [10]

33 9.3.4 最大堆的初始化 a = [20,12,35,15,10,80,30,17,2,1] n=10, n/2=5 [1] [3]
最大堆的初始化 a = [20,12,35,15,10,80,30,17,2,1] n=10, n/2=5 [1] 20 [3] [2] 12 35 [5] [7] [4] [6] 15 10 80 30 i 17 2 1 [10] [8] [9] 33

34 [1] 20 [3] [2] 12 35 [5] [4] [6] 17 10 80 30 15 2 1 [10] [8] [9]

35 [1] 20 [3] 12 [2] 80 [5] [4] [6] 17 10 35 30 i 15 2 1 [10] [8] [9]

36 [1] 20 [3] [2] 17 80 [5] [4] [6] 15 10 35 30 i 12 2 1 [10] [8] [9]

37 [1] 80 [3] [2] 17 20 [5] [4] [6] 15 10 35 30 i 12 2 1 [10] [8] [9]

38 [1] 80 [3] [2] 17 35 [5] [4] [6] 15 10 20 30 i 12 2 1 [10] [8] [9]

39 9.3.5 类MaxHeap template <classT> class MaxHeap{ public:
MaxHeap(int MaxHeapSize = 10); ~MaxHeap( ) {delete [] heap;} int Size( ) const {return CurrentSize;} //返回元素数 T Max( ) //取最大值 {if (CurrentSize = = 0) throw OutOfBounds( ); return heap[1];} MaxHeap<T>& Insert(const T& x); MaxHeap<T>& DeleteMax(T& x); void Initialize(T a[], int size, int ArraySize); private: int CurrentSize, MaxSize; T *heap; // 指向一维数组的指针，heap是一维数组的名 } ;

40 堆是完全二叉树，可用一维数组有效地描述堆.
9 8 6 7 2 5 1 …… currentsize Maxsize heap

41 MaxHeap构造函数 template<class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize) {// 构造函数 MaxSize = MaxHeapSize; heap = new T[MaxSize+1]; CurrentSize = 0; }

42 template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x) {// 把x 插入到最大堆中 if (CurrentSize = = MaxSize) throw NoMem(); // 没有足够空间 //为x寻找应插入位置 // i 从新的叶节点开始，并沿着树上升 int i = ++CurrentSize; //新的空位置 while (i != 1 && x > heap[i/2]) { //不能够把x放入heap[i] heap[i] = heap[i/2]; // 将元素下移 i /= 2; // 指针移向父节点 } heap[i] = x; return *this;

43 template<class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x) {// 将最大元素放入x ，并从堆中删除最大元素 if (CurrentSize = = 0) throw OutOfBounds(); // 检查堆是否为空 x = heap[1]; // 取走最大元素 // 重构堆 T y = heap[CurrentSize--]; // 先取最后元素，然后修改指针 // 从根开始，自上而下的为y 寻找合适的位置 int i = 1, // current node of heap ci = 2; // left child of i while (ci <= CurrentSize) { if (ci < CurrentSize && heap[ci] < heap[ci+1]) ci++; //ci是值大的孩子 if (y >= heap[ci]) break;//大于两个孩子了，退出寻找位置循环， heap[i] = heap[ci]; // 否则将ci代表的孩子上移 i = ci; //沿ci为根的子树继续寻找放入位置 ci *= 2; } heap[i] = y; return *this;

44 if (c < CurrentSize && heap[c] < heap[c+1]) c++）
void MaxHeap<T>::Initialize(T a[], int size, int ArraySize) {// 把数组a初始化为最大堆. delete [] heap; heap = a; CurrentSize = size; MaxSize = ArraySize;//按用户需求定义堆的大小 // 产生一个最大堆 for (int i = CurrentSize/2; i >= 1; i--) {// 从n/2位置开始调整初始堆 T y = heap[i]; // i 为需要调节子树的根,暂时取出，留个工作位置 // 根值暂时放在y int c = 2*i; // c为i 的左儿子 while (c <= CurrentSize) { // heap[c] 应是较大的同胞节点 if (c < CurrentSize && heap[c] < heap[c+1]) c++） if (y >= heap[c]) break; // 不需要调节，退出循环 // 沿以ci为根的子树向下调节，利用while循环，只需改变根 heap[c/2] = heap[c]; // 将孩子上移.第一次放在 i的位置 c *= 2; // 下移一层 } heap[c/2] = y;

45 Initialize(T a[], int size, int ArraySize)把数组a初始化为最大堆。
为避免调用堆的析构函数时将数组a删除，在MaxHeap类中增加Deactive(使得无效）函数。 Void Deactive() {heap=0;}

46 初始化堆的时间复杂性: 堆的高度 = h. 在j层节点的数目 <= 2j-1. 以j层节点为根的子树的高度 = h-j+1 调整（或重构）以j层节点为根的子树时间（高度）O(h-j+1). 调整（或重构）所有以j层节点为根的子树： <= 2j-1(h-j+1) = t(j). 总的时间： t(1) + t(2) + … + t(h-1)=O( = =O(2h) =O(n).

47 Leftist tree（左高树） Despite the heap is both space and time efficient, it is not suitable for all applications of priority queues, i.e., combine or blend（混合） pairs of priority queues, as well as those in which we have multiple queues of varying size. Leftist tree structures are suitable for these applications

48 9.4 左高树(Leftist Trees) 左高树 高度优先左高树(HBLT— height-biased leftist tree )
重量优先左高树(WBLT —weight-biased leftist tree) 最大/最小 WBLT

49 Consider a binary tree in which a special node called an external node replaces each empty tree. The remaining nodes are called internal node. A binary tree with external nodes added is called an extended binary tree.

50 扩充二叉树(Extended Binary Tree)
外部节点( External node) –代替树中的空子树的节点。 内部节点( Internal node) – 具有非空子树的节点。 扩充二叉树( Extended binary tree) –增加了外部节点的二叉树.

51 例：一个二叉树

52 扩充二叉树 外部节点的数目是： n+1

53 函数 s() Let S(x) be the length of a shortest path from node x to an external node in its subtree.

54 s()的计算 x是外部节点，则 s(x) = 0. 否则, s(x) = min {s(L), s(R)} + 1
其中L与R分别为x的左右孩子。 s() values may be computed easily using a postorder traversal. 54 54

55 s()的值 1 2

56 高度优先左高树 (HBLT) 定义[高度优先左高树] 当且仅当一棵二叉树的任何一个内部节点，其左孩子的s 值右孩子的s 值时，该二叉树为高度优先左高树（height-biased leftist tree, HBLT）。 对每一个内部节点 x, s(L) >= s(R),其中L与R分别为x的左右孩子。 图所示的二叉树是 HBLT?

57 一个左高树 1 2

58 高度优先左高树 (HBLT) 定理9-1：令x 为一个HBLT的内部节点，则 (a)以x 为根的子树的节点数目至少2s(x) – 1
(b)若以x 为根的子树有m 个节点，则s(x)最多为log2(m+1) (c)通过最右从x到达外部节点的路径（即，此路径是从x 开始沿右孩子移动）的路径长度为s(x) . 证明：s (x) 对应于以x节点为根的一个完全2叉子树子树的高度，而满2叉树的顶点数为2s(x) – 1 。而以x为根的子树还可能有其他节点，故根据满2叉树的性质，a)和b)成立。C)根据函数 s的定义：s(x) = min {s(L), s(R)} + 1，以及在HBLT中，s(L)s(R), 故c成立。即最短路一定在沿着右孩子的方向上。

59 最大/最小 HBLT Definition A max HBLT is an HBLT that is also a max tree. A min HBLT is an HBLT that is also a min tree.

60 最大/最小 HBLT 定义[最小HBLT] 即同时又是最小树的HBLT 。

61 重量优先左高树 (WBLT) 定义x的重量w(x), 为以x 为根的子树的内部节点数目。
定义[重量优先左高树]（ WBLT—weight-biased leftist tree, ）：当且仅当一棵二叉树的任何一个内部节点，其左孩子的w 值大于等于右孩子的w 值时。 [最大（小）WBLT] 该二叉树为重量优先左高树即同时又是最大（小）树的WBLT。

62 重量优先左高树 (WBLT) Not a WBLT

63 Operations on HBLTs Since the way in which finds, insert, delete, meld and initializations are done in WBLTs and HBLTs is similar, consequently we describe these operations for HBLTs only.

64 Insert and delete for HBLT
insertion element x into a Max HBLT H 1) create a max HBLT T with x only 2) meld (合并) two Max HBLT H and T into a new Max HBLT Deletion from a Max HBLT H 1) delete the root of H; 2) meld two max HBLT leftsubtree and rightsubtree into a new Max HBLT

65 Melding two max HBLTs recursively
Let A and B be the two max HBLTs being melded. If (A or B =empty) then return the nonempty one else { root = max{root(A),root(B)}; let A be the tree with the max roots, L is its left subtree, then meld the right subtree of A and B into C; If the s value of L is smaller than that of C then let C be the left subtree; A as its root and L be the right subtree; otherwise exchange C and L in the above processing.

66 A A C B AL AR C? AL?

67 1 S=1 9 1 7 1 9 7 1 a b c 1 2 1 10 10 7 1 1 7 1 5 5 e d

68 1 2 18 10 1 6 1 1 7 5 f 18 6 10 7 5

69 MAX HBLT的插入 对给定元素x，插入到MAX HBLT H 中 1) 建立一棵仅含有x的树 B； 2）meld (H,B)

70 9.4.2 最大HBLT的插入 Insert(7) 6 4 2 8 3 5 9

71 9.4.2 最大HBLT的插入 Insert(7) 6 4 2 8 3 5 9 7 创建一棵单元素最大HBLT.

72 9.4.2 最大HBLT的插入 Insert(7) 6 4 2 8 3 5 9 7

73 最大HBLT删除 最大HBLT H, 删除元素应该是H 的根（具有最大值），meld (Lefttree(H),Righttree(H))

74 9.4.3 最大HBLT的删除 6 4 2 8 3 5 9

75 9.4.3 最大HBLT的删除 9 具有最大的根 6 4 8 2 3 5 删除根节点. 合并两棵子最大HBLT。

76 9.4.3 最大HBLT的删除 具有最大的根 6 4 8 5 3 2

77 9.4.4 合并两颗最大HBLT

78 9.4.5 初始化最大HBLT 方法1. 通过将n 个元素插入到最初为空的最大HBLT中来对其进行初始化. 时间为:O(nlogn)

79 9.4.5 初始化最大HBLT 时间复杂性: O(n) 方法2.
1、创建n 个最大HBLT ，每个树中仅包含n 个元素中的某一个，这n 棵树排成一个FIFO队列， 2、从队列中依次删除两个最大HBLT ，将其合并，然后再加入队列末尾。 重复第2步，直到最后只有一棵最大HBLT 。 时间复杂性: O(n)

80 9.4.5 初始化最大HBLT 元素:7,1, 9, 11,2 7 1 9 11 2 7 1 9 11 2

81 9.4.5 初始化最大HBLT 7 1 9 11 2 7 1 9 11 2 7 1 9 11 2 81

82 9.4.5 初始化最大HBLT 时间复杂性 为简单起见，假设n 是2的幂次方。
合并n / 2对具有1个元素的最大HBLT，每次合并O(1)。 合并n/ 4对含有2个元素的最大HBLT ，每次合并O(2)。 合并n/ 8对含有4个元素的最大HBLT ，每次合并O(3)。 ⋯ ⋯ 。 合并两棵含2i 个元素的最大HBLT，每次合并O(i+1)， 合并1对含n/2 (2k-1)个元素的最大HBLT,每次合并O(k) 因此总时间为： O(n/2+2*(n/4)+3*(n/8)+…+k*(n/2h)) = O(ni/2i)=O(n)

83 9.4.6 类MaxHBLT 程序9-6 HBLT的节点类 程序9-7 MaxHBLT类 程序9-8 合并两棵左高树

84 程序9-6 HBLT的节点类 class HBLTNode { friend MaxHBLT < T > ; public:
HBLTNode(const T& e, const int sh)//构造函数只需2个参数 {data = e; s = sh; LeftChild = RightChild = 0;} private: int s; // 节点的s 值 T data; HBLTNode<T> *LeftChild, *RightChild; } ;

85 程序9-7 MaxHBLT类 template<class T> class MaxHBLT { public:
MaxHBLT() {root = 0;} ~MaxHBLT() {Free(root);} T Max() {if (!root) throw OutOfBounds(); return root->data;} MaxHBLT<T>& Insert(const T& x); MaxHBLT<T>& DeleteMax(T& x); MaxHBLT<T>& Meld(MaxHBLT<T>& x) { Meld(root, x.root); x.root = 0; //禁止对x为根的子树访问 return *this;} void Initialize(T a[], int n); private: void Free(HBLTNode<T> *t); void Meld(HBLTNode<T>* &x, HBLTNode<T>* y); HBLTNode<T> *root; // 指向树根的指针 } ; 程序9-7 MaxHBLT类 x和本树合并

86 程序9-8 合并两棵左高树 template<class T>
void MaxHBLT<T>::Meld(HBLTNode<T>* &x, HBLTNode<T>* y) {// 合并两棵根分别为* x和* y的左高树, 返回指向新根x的指针 if (!y) return; // y 为空 if (!x) // x为空 {x = y; return;} // x和y 均为空 if (x->data < y->data) Swap(x,y); // 现在x->data >= y->data Meld(x->RightChild, y ) ; //递归先把x的右子树与y归并，并作为x的右子树

87 程序9-8 合并两棵左高树(续) if (!x->LeftChild) {// 左子树为空 // 交换子树
x->LeftChild = x->RightChild; x->RightChild = 0; x->s = 1;} //无右孩子 else {// 检查是否需要交换子树 if (x->LeftChild->s < x->RightChild->s) Swap(x->LeftChild,x->RightChild); x->s = x->RightChild->s + 1;}//修改x自身的s值 }

88 Insert template<class T>
MaxHBLT<T>& MaxHBLT<T>::Insert(const T &x) {// Insert x into the leftist tree // Creat a tree with one node HBLTNode<T> *q= new HBLTNode<T> (x,1) //根据其构造函数x =data, s=1, 左右儿子为空 // meld q and original tree Meld (root,q); Return *this; }

89 Delete template<class T>
MaxHBLT<T>& MaxHBLT<T>::DeleteMax(T &x) {// Delete the Max element and put it in x if (!root) throw OutOfBounds(); x=root->data; HBLTNode<T> *L = root->LeftChild; HBLTNode<T> *R = root->RightChild; Delete root; root = L; Meld (root,R) Return *this; }

90 Initialization Q.Add(q); }//n 个一个顶点的左高树加入到Q template<class T>
Void MaxHBLT<T>::Initialize(T a[], int n) {Queue<HBLTNode<T> *> Q(n);//difne a Queue with size=n Free(root); for (int i=1; i<=n; i++) { HBLTNode<T> *q = new HBLTNode<T> (a[i],1); Q.Add(q); }//n 个一个顶点的左高树加入到Q //repeat meld from Q HBLTNode<T> *b, *c; for (int i=1, i<=n-1; i++) { Q.Delete(b).Delete(c ); //从Q中连续取出2个左高树 Meld(b,c) ; Q.Add(b); }; //当循环结束时，Q中只完成合并的树，n>1 If (n) Q.Delete(root); // n>1时，把最终合并的树指针赋值给root }

91 9.5 应用 9.5.1 堆排序 9.5.2 机器调度 9.5.3 霍夫曼编码

92 9.5.1 堆排序(Heap Sort) 可利用堆来实现n个元素的排序，每个元素的关键值为优先权。 堆排序算法：
每次从堆中提取（即删除）元素。 如果使用最大堆,各元素将按非递增次序排列。 如果使用最小堆,各元素将按非递减次序排列。

93 例：堆排序 A=[20,12,35,15,10,80,30,17,2,1] 2 80 30 17 35 1 20 10 12 15

94 例：堆排序 初始化最大堆 2 20 30 12 35 1 80 10 17 15

95 例：堆排序 80 35 30 20

96 堆排序实现 template <class T> void HeapSort(T a[], int n)
{// 利用堆排序算法对a[1:n] 进行排序 MaxHeap<T> H(1); H.Initialize(a,n,n); // 创建一个最大堆 // 从最大堆中逐个抽取元素 T x; for (int i = n-1; i >= 1; i--) { H.DeleteMax(x); a[i+1] = x; } H.Deactivate(); // 在堆的析构函数中保存数组a

97 堆排序的时间复杂性分析 对n 个元素进行排序： 初始化所需要的时间为：(n) 每次删除所需要的时间为： O(logn)
因此总时间为： O(nlogn)//n次循环

98 9.5.3 霍夫曼编码(Huffman Codes) 基于LZW算法的文本压缩工具，利用了字符串在文本中重复出现的规律。

99 字符编码 假设: 每个字符用一个byte(8bit)来存贮. 每个字符用2bit编码来存贮. 文本是由a,x, u, z组成的字符串;
这个字符串的长度为:1000 每个字符用一个byte(8bit)来存贮. 字符串: 字符，1000byte（8000bit). 每个字符用2bit编码来存贮. 字符串: 字符，2000byte. a:00; x:01; u: 10; z:11 字符串: 2000位，可以减少 6000bit

100 霍夫曼编码 不采用均匀对每个符号分配bit数，而是给出现频率高的字符短编码，出现频率低的长编码。
E.g. 采用均匀编码，每个字符的编码长度= log2 (符号个数) aaxuaxz  log(4)=2, a=00,x=01,u=10,z=11 (编码总长度:14bits) a（frequency 3), x(2), u(1), z(1) a=0, x=10, u=110, z=111 (13 bit), 若(996,2,1,1), 则按频率为1006bit，2位编码2000 bit

101 霍夫曼编码 霍夫曼编码根据不同符号在一段文字中的相对出现频率来设计压缩编码。 频率(frequency):一个字符出现的次数称为频率 .
aaxuaxz: 频率: a:3 x: u: z:1

102 霍夫曼树(Huffman Trees) 扩充二叉树的加权外部路径长度(Weighted External Path length ) :
L(i) —从根到达外部节点i 的路径长度（即路径的边数）； F(i) —外部节点i 的权值(weight) . 如果F(i)是字符串中被编码的字符的频率, WEP 就是压缩编码串的长度. 霍夫曼树：对于给定的频率具有最小加权外部路径长度 的二叉树。 102

103 构造霍夫曼树 构造霍夫曼树： 1. 初始化二叉树集合，每个二叉树含一个外部节点，每个外部节点代表字符串中一个不同的字符,外部节点的权重为频率. 2. 从集合中选择两棵具有最小权重的二叉树，并把它们合并成一棵新的二叉树。合并方法是把这两棵二叉树分别作为左右子树，然后增加一个新的根节点。新二叉树的权重为两棵子树的权重之和。 3.重复第2步，直到仅剩下一棵树为止。 4. 从根向下，对每个顶点，若有孩子，则分配左儿子边为0，右面为1。 5.每个字符的编码为从根到对应外部节点路径上的字符串。 103

104 构造霍夫曼树示例 104

105 a: 00 b: 010 c: 011 d: 100 e: 101 f: a b c d e f 27 1 105

106 利用霍夫曼编码进行文本压缩编码 利用霍夫曼编码对字符串或一段文本进行压缩编码：
1.确定不同字符的频率。 2. 建立具有最小加权外部路径的二叉树（即霍夫曼树），树的外部节点用字符串中的字符表示，外部节点的权重（weight）即为该字符的频率。 3.遍历从根到外部节点的路径得到每个字符的编码。 4.用字符的编码来代替字符串中的字符。

107 构造霍夫曼树的实现 使用一个最小堆来存储二叉树集合。 最小堆的每个元素包括两部分： template<class T>
二叉树的权值. template<class T> class Huffman { friend BinaryTree<int> HuffmanTree(T[],int); public: operator T() const {return weight;} private: BinaryTree<int> tree; T weight; };

108 template <class T>
BinaryTree <int> HuffmanTree(T a[],int n) {// 根据权重a [1 : n]构造霍夫曼树 // 创建一个单节点树的数组 Huffman<T> *w = new Huffman<T> [n+1]; BinaryTree<int> z, zero; for (int i = 1; i <= n; i++) { z.MakeTree(i,zero,zero);//i = 树的编号 w[i].weight = a[i];//频率数 w[i].tree = z; } // 把数组变成一个最小堆 MinHeap <Huffman<T> > H(1); H.Initialize(w,n,n);

109 //将堆中的树不断合并 Huffman <T> x,y; for(i=1;i<n;i++){ H.DeleteMin(x); H.DeleteMin(y); z.MakeTree(0,x.tree,y.tree);//形成新树z, 0没特殊意义 x.weight+=y.weight; x.tree=z; H.Insert(x); //把合并树加入到堆中，树的数目-1 } H.DeleteMin(x);//最后的树 H.Deactivate( ); delete[]w; Return x.tree;

110 作业：8，9，14，16，23

111 练习题 1. 一组序列的关键码为： {28、19、27、49、56、12、10、25} 2.在一段文字中，7个常用汉字及出现频度如下：
该序列是否是堆？若不是，写出建立的初始堆（最大堆）。 利用堆排序的方法对该序列进行非递减排列，给出堆排序的主要过程。 给出在初始堆中插入一新元素60后的堆结构。 2.在一段文字中，7个常用汉字及出现频度如下： 的 地 于 个 和 是 有 要求： ⑴ 画出对应的Huffman树； ⑵ 求出每个汉字的Huffman编码。

112 练习题 1. 一组序列的关键码为： {28、19、27、49、56、12、10、25} 2.在一段文字中，7个常用汉字及出现频度如下：
该序列是否是堆？若不是，写出建立的初始堆（最大堆）。 利用堆排序的方法对该序列进行非递减排列，给出堆排序的主要过程。 给出在初始堆中插入一新元素60后的堆结构。 2.在一段文字中，7个常用汉字及出现频度如下： 的 地 于 个 和 是 有 要求： ⑴ 画出对应的Huffman树； ⑵ 求出每个汉字的Huffman编码。