Chapter9 Priority Trees

Slides:



Advertisements
Similar presentations
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
Advertisements

阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
计算机软件技术基础 数据结构与算法(4).
数据结构学习考 复习课(2) 主要内容: 第三部分:树、二叉树、森林.
引入树 线性表、堆栈和队列都是线性结构,它们的共同特点:一对一; 计算机对弈中的一个格局可能有多个后继格局,用线性结构难以描述。
助教:李伟力 电子科学与技术系 数据结构第二次习题课 助教:李伟力 电子科学与技术系
第5章 树( Tree )和二叉树 5.1 树的基本概念 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林
数据结构与算法 Data Structure Algorithms
第六章 二叉树和树 6.1 二叉树 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林
第六章 树和森林 1、树、森林的概念 2、二叉树及其表示 3、遍历二叉树和线索二叉树 4、堆 5、树和森林 6、二叉树的计数 7、霍夫曼树
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
树(三) 2012初赛知识点梳理.
树和二叉树(四).
Chapter 5 Tree & Binary Tree
Hadoop I/O By ShiChaojie.
Chapter8 Binary and Other Trees
第五章 树与二叉树 树和森林的概念 二叉树 二叉树遍历 线索化二叉树 树与森林 堆 Huffman树.
第9章 优先队列(Priority Queues)
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
第七章 搜索结构 静态搜索结构 二叉搜索树 AVL树.
哈夫曼编码.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
Chapter 6 队列(QUEUES).
第8章 树和二叉树 树 二叉树 二叉树设计 二叉树遍历 线索二叉树 哈夫曼树 等价问题 树与二叉树的转换 树的遍历 主要知识点.
第5章 树和二叉树 5.1树 5.2二叉树 5.3二叉树的遍历 5.4线索二叉树 5.5树、森林与二叉树的转换 5.6哈夫曼树.
第11讲 树和二叉树(二).
第六章 树与森林 树和森林的概念 二叉树 (Binary Tree) 二叉树的表示
第五章 树 5.1 树的定义 树是一类重要的非线性数据结构,是以分支关系定义的层次结构 定义
Tree & Binary Tree.
Chapter6 队列(Queues) The Abstract Data Type
Tree & Binary Tree.
顺序表的插入.
使用矩阵表示 最小生成树算法.
2.1.2 空间中直线与直线 之间的位置关系.
无向树和根树.
二叉树的遍历.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
顺序表的删除.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
第九章 排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排序 归并排序.
第二章 Java基本语法 讲师:复凡.
复习.
Lightweight Data-flow Analysis for Execution-driven Constraint Solving
信号量(Semaphore).
第六章 树和二叉树.
iSIGHT 基本培训 使用 Excel的栅栏问题
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.16 枚举算法及其程序实现 ——数组的作用.
树和图 tree and graph 蔡亚星.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第七、八次实验要求.
树和二叉树(四).
十二、堆 堆的定义.
#define RBTREE_RED 0 #define RBTREE_BLACK 1 typedef int dataType; typedef struct treeNode{ dataType key; int color; //red:0.
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
生 物 信 息 学 Bioinformatics 巩晶 癌症研究中心 山东大学 医学院
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
插入排序的正确性证明 以及各种改进方法.
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
第七章 搜索结构 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
§4.5 最大公因式的矩阵求法( Ⅱ ).
本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司
第二次课后作业答案 函数式编程和逻辑式编程
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
第五章 树和二叉树.
Presentation transcript:

Chapter9 Priority Trees 堆(Heaps) 左高树(Leftist Trees) 11/19/2018

本章重点 堆的实现 堆排序 左高树 霍夫曼编码 11/19/2018

优先队列 与FIFO结构的队列不同,优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序,而不是元素进入队列的次序。 例。 11/19/2018

优先队列 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值。 对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除 11/19/2018

优先队列的线性表描述 描述最大优先队列最简单的方法是采用无序线性表。 假设有一个具有n 个元素的优先队列,插入操作可以十分容易地在表的右端末尾执行,插入所需时间为Θ(1)。删除操作时必须查找优先权最大的元素,即在未排序的n 个元素中查找具有最大优先权的元素,所以删除操作所需时间为Θ(n)。 11/19/2018

优先队列的线性表描述 如果利用链表,插入操作在链头执行,时间为Θ(1),而每个删除操作所需时间为Θ(n)。 11/19/2018

优先队列的线性表描述 另一种描述方法是采用有序线性表,当使用公式化描述时元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为Θ(1),插入操作所需时间为Θ(n)。 11/19/2018

最大树 定义 每个节点的值都大于或等于其子节点(如果有的话)值的树。 11/19/2018

最大树 11/19/2018

最小树 定义 每个节点的值都小于或等于其子节点(如果有的话)值的树。 11/19/2018

最小树 11/19/2018

最大堆(最小堆) 定义 最大(最小)的完全二叉树。 11/19/2018

最大堆的插入 11/19/2018

插入时间复杂性 插入策略从叶到根只有单一路径,每一层的工作需耗时Θ(1),因此实现此策略的时间复杂性为O(height)=O(log2n)。 11/19/2018

最大堆的删除 11/19/2018

最大堆的删除 11/19/2018

删除时间复杂性 删除策略产生了一条从堆的根节点到叶节点的单一路径,每层工作需耗时Θ(1),因此实现此策略的时间复杂性为O(height)=O(log2n)。 11/19/2018

最大堆的初始化 开始时堆中已经含有n (n >0) 个元素。可以通过在初始为空的堆中执行n 次插入操作来构建非空的堆,插入操作所需总时间为O(nlogn) 。 11/19/2018

思考 更快的堆的初始化策略? 11/19/2018

思想 从第一个具有孩子的节点开始,这个元素在数组中的位置为i=[n/2],如果以这个元素为根的子树已是最大堆,则此时不需调整,否则必须调整子树使之成为堆。 随后,继续检查以i-1,i-2等节点为根的子树,直到检查到整个二叉树的根节点(其位置为1)。 11/19/2018

最大堆的初始化 11/19/2018

最大堆的初始化 11/19/2018

类MaxHeap template<class T> 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; // 元素数组 } ; 11/19/2018

最大堆的插入 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; 11/19/2018

最大堆的删除 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, //堆的当前节点 ci=2;//i的孩子 11/19/2018

最大堆的删除 while (ci<=CurrentSize) { //heap[ci]应该是i较大的孩子 if(ci<CurrentSize && heap[ci]<heap[ci+1]) ci++; //能把y放入heap[i]吗? if (y>=heap[ci]) break; //能 //不能 heap[i]=heap[ci]; i=ci; ci*=2; } heap[i]=y; return *this; 11/19/2018

Leftist Trees(左高树) 堆结构是一种隐式数据结构,用完全二叉树表示的堆在数组中是隐式存贮的。由于没有存贮结构信息,这种描述方法空间利用率很高。 尽管堆结构的时间和空间效率都很高,但它不适合于所有优先队列的应用,尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用,左高树就能满足这种要求。 11/19/2018

扩充二叉树 一棵二叉树,它有一类特殊的节点叫做外部节点(external node),用来代替树中的空子树,其余节点叫做内部节点(internal node)。 增加了外部节点的二叉树被称为扩充二叉树(extended binary tree)。 11/19/2018

扩充二叉树 11/19/2018

s 令s(x)为从节点x 到它的子树的外部节点的所有路径中最短的一条,根据s(x)的定义可知,若x是外部节点,则s的值为0,若x为内部节点,则它的s值是: min{s(L),s(R)} + 1 其中L与R分别为x 的左右孩子。 11/19/2018

扩充二叉树的s和w 11/19/2018

高度优先左高树 定义 当且仅当一棵二叉树的任何一个内部节点,其左孩子的s 值大于等于右孩子的s 值时,该二叉树为高度优先左高树(height-biased leftist tree, HBLT)。 11/19/2018

高度优先左高树-性质 定理9-1 令x 为一个HBLT的内部节点,则 以x 为根的子树的节点数目至少为2s(x)-1。 若子树x 有m 个节点,s(x)最多为log2(m+1)。 通过最右路径(即,此路径是从x 开始沿右孩子移动)从x 到达外部节点的路径长度为s (x)。 11/19/2018

最大HBLT/最小HBLT [最大HBLT] 即同时又是最大树的HBLT; [最小HBLT] 即同时又是最小树的HBLT。 11/19/2018

最大HBLT的操作 插入 删除 合并 初始化 11/19/2018

最大HBLT的插入 最大HBLT的插入操作可借助于最大HBLT的合并操作来完成。 假设将元素x插入到名为H的最大HBLT中,如果建造一棵仅有一个元素x的最大HBLT然后将它与H进行合并,结果得到的最大HBLT将包括H中的全部元素及元素x。因此插入操作只需先建立一棵仅包含欲插入元素的HBLT,然后将它与原来的HBLT合并即可。 11/19/2018

最大HBLT的删除 根是最大元素,如果根被删除,将留下分别以其左右孩子为根的两棵HBLT的子树。将这两棵最大HBLT合并到一起,便得到包含除删除元素外所有元素的最大HBLT。 所以删除操作可以通过删除根元素并对两个子树进行合并来实现。 11/19/2018

合并两棵最大HBLT 具有n个元素的最大HBLT,其最右路径的长度为O(logn)。合并操作仅需遍历欲合并的HBLT的最右路径。由于在两条最右路径的每个节点上只需耗时O(1),因此将两棵HBLT进行合并具有对数复杂性。 通过以上观察,在合并算法中,仅需移动右孩子。 11/19/2018

合并两棵最大HBLT 合并策略最好用递归来实现。 令A、B为需要合并的两棵最大HBLT,如果其中一个为空,则将另一个作为合并的结果,因此可以假设两者均不为空。 为实现合并,先比较两个根元素,较大者作为合并后的HBLT的根。假定A具有较大的根,且其左子树为L,C是由A的右子树与B合并而成的HBLT。A与B合并所得结果即是以A的根为根,L与C为左右子树的最大HBLT。如果L的s值小于C的s值,则C为左子树,否则L为左子树。 11/19/2018

最大HBLT的合并 11/19/2018

最大HBLT的合并 11/19/2018

初始化最大HBLT 通过将n个元素插入到最初为空的最大HBLT中来对其进行初始化,所需时间为O(nlogn)。 更快的方法? 11/19/2018

初始化最大HBLT 为得到具有线性时间的初始化算法,首先创建n个最大HBLT,每个树中仅包含n个元素中的某一个,这n棵树排成一个FIFO队列,然后从队列中依次删除两个HBLT,将其合并,然后再加入队列末尾,直到最后只有一棵HBLT。 11/19/2018

例 构造五个元素:7,1,9,11,2的一棵最大HBLT。 首先构造五个单元素的最大HBLT,并形成一个FIFO队列。 11/19/2018

合并两棵左高树 template<class T> void MaxHBLT<T>::Meld(HBLTNode<T>* &x,HBLTNode<T>* y) {//合并两棵根分别为*x和*y的左高树,返回指向新根x的指针 if(!y) return; if(!x) {x=y; return;} if(x->data < y->data) Swap(x,y); Meld(x->RightChild,y); 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; } 11/19/2018

从最大HBLT中删除最大元素 template<class T> MaxHBLT<T>& MaxHBLT<T>::DeleteMax(T& x) {//删除最大元素,并将其放入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; } 11/19/2018

最大HBLT的初始化 template<class T> void MaxHBLT<T>::Initialize(T a[], int n) {//初始化有n个元素的HBLT树 Queue<HBLTNode<T> *> Q(n); Free(root);//删除老节点 //对树的队列进行初始化 for (int i=1;i<=n;i++){ HBLTNode<T> *q=new HBLTNode<T> (a[i],1); Q.Add(q);} HBLTNode<T> *b,*c; for (i=1;i<=n-1;i++) {Q.Delete(b).Delete(c); Meld(b,c); Q.Add(b);} if (n) Q.Delete(root); } 11/19/2018

应用 堆排序(Heap Sort) 机器调度(Machine Scheduling) 霍夫曼编码(Huffman Codes) 11/19/2018

堆排序 先将要排序的n 个元素初始化为一个最大堆,然后每次从堆中提取(即删除)元素。各元素将按递减次序排列。 初始化所需要的时间为(n),每次删除所需要的时间为O(logn) ,因此总时间为O(nlogn) 。 11/19/2018

堆排序算法实现 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; } 11/19/2018

堆排序算法实现 // 在堆的析构函数中保存数组a H.Deactivate(x) ; } 11/19/2018

堆排序 11/19/2018

例-压缩 假设文本是由a,u,x,z组成的字符串,若这个字符串的长度为1000,每个字符用一个字节来存贮,共需1000个字节(即8000位)的空间。如果每个字符用2位二进制来编码(00=a,01=x,10=u,11=z),则用2000位二进制即可表示1000个字符。 字符串aaxuaxz的压缩编码为二进制串0000011000011。 11/19/2018

例 此外,还需要一定的空间来存放编码表,可采用如下格式来存储: 符号个数,代码1,符号1,代码2,符号2,… 符号个数及每个符号分别用8位二进制来表示,每个代码需占用[log2(符号个数)]位二进制。因此,代码表需占用5*8+4*2=48位,压缩比为8000/2048=3.9。 11/19/2018

例-解压 字符串aaxuaxz的压缩编码为二进制串00000110000111,每个字符的编码具有相同的位数(两位)。 从左到右依次从位串中取出2位,通过查编码表便可获得原字符串。 11/19/2018

频率 一个字符出现的次数称为频率(frequency) 在字符串aaxuaxz中,a出现了三次。 a,x,u,z,在这个字符串中出现的频率分别为3,2,1,1。 11/19/2018

方案 采用可变长编码。 使用编码(0=a,10=x,110=u,111=z) 。如果四个字符的出现频率分别为(996,2,1,1),则每个字符用2位编码所得到编码的长度为2000位,而用可变长编码则仅为1006位。 11/19/2018

解码依据 可变长编码:没有任何一个代码是另一代码的前缀。 因此,当从左到右检查代码时,可以很确定地得到与实际代码相匹配的字符。 11/19/2018

霍夫曼编码 可以利用扩充二叉树来派生一个实现可变长编码的特殊类,该类满足上述前缀性质,被称为霍夫曼编码。 11/19/2018

霍夫曼编码 在扩充二叉树中,可对从根到外部节点的路径进行编码,方法是向左孩子移动时取0,向右孩子移动时取1。 11/19/2018

霍夫曼编码 到节点(a,b,c,d,e,f)的路径编码分别为(00,010,011,100,101,11) 11/19/2018

加权外部路径长度 对于一棵具有外部节点1,… n 的扩充二叉树,对应的压缩编码串的长度为: 其中L(i) 为从根到达外部节点i 的路径长度(即路径的边数);F(i)为外部节点i 的权值(压缩中字符的频率);WEP为二叉树的加权外部路径长度(weighted external path length)。 11/19/2018

带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中,权值大的结点离根最近。 具有不同带权路径长度的扩充二叉树 霍夫曼树 带权路径长度达到最小的扩充二叉树即为霍夫曼树。 在霍夫曼树中,权值大的结点离根最近。 11/19/2018

霍夫曼树 若二叉树对于给定的频率具有最小加权外部路径长度,则这棵树被称为霍夫曼树(Huffman tree)。 11/19/2018

利用霍夫曼编码进行压缩 获得不同字符的频率。 建立具有最小加权外部路径的二叉树(即霍夫曼树),树的外部节点用字符串中的字符表示,外部节点的权重(weight)即为该字符的频率。 遍历从根到外部节点的路径得到每个字符的编码。 用字符的编码来代替字符串中的字符。 11/19/2018

构造霍夫曼树 为了构造霍夫曼树,首先从仅含一个外部节点的二叉树集合开始,每个外部节点代表字符串中一个不同的字符,其权重等于该字符的频率。 此后不断地从集合中选择两棵具有最小权重的二叉树,并把它们合并成一棵新的二叉树,合并方法是把这两棵二叉树分别作为左右子树,然后增加一个新的根节点。新二叉树的权重为两棵子树的权重之和。 这个过程可一直持续到仅剩下一棵树为止。 11/19/2018

构造霍夫曼树 11/19/2018

构造霍夫曼树 权重=27。到节点(a,b,c,d,e,f)的路径编码分别为(00,010,011,100,101,11) 11/19/2018

霍夫曼树 霍夫曼树的建立过程可以利用最小堆来实现。 最小堆用来存贮二叉树集合。 最小堆中的每个元素包括一棵二叉树及其权重值, 11/19/2018

输出二叉树上从根到所有叶子结点的路径 void AllPath( BiTree T, Stack& S ) { if (T) { Push( S, T->data ); if (!T->Lchild && !T->Rchild ) PrintStack(S); else { AllPath( T->Lchild, S ); AllPath( T->Rchild, S ); } Pop(S); } // if(T) } // AllPath 11/19/2018

输出二叉树上从根到所有叶子结点的路径 void AllPath( BiTree T, Stack& S, bool flag ) { if (T) { if (T->data ) {PrintStack(S);} else {if (flag ) {Push( S, 0 ); AllPath( T->Lchild, S,0 );} else { Push( S, 1 ); AllPath( T->Rchild, S ,1); } }} Pop(S); } // if(T) } // AllPath 11/19/2018

作用 1、编码 2、优化程序 3、归并排序 11/19/2018

字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。 霍夫曼编码 主要用途是实现数据压缩。 设给出一段报文: CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T },各个字符出现的频度(次数)是 W={ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码,可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。 11/19/2018

化整为 { 2, 7, 4, 5 },以它们为各叶结点上的权值,建立霍夫曼树。左分支赋 0,右分支赋 1,得霍夫曼编码(变长编码)。 A : 0 T : 10 C : 110 S : 111 它的总编码长度:7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 霍夫曼编码是一种无 前缀编码。解码时不会 混淆。 霍夫曼编码树 11/19/2018

编制分数转化程序 if (a<60) b=‘不及格’ else if (a<70) b=‘及格’ else b=‘优秀’ 11/19/2018

作业 分数 0-59 60-69 70-79 80-89 90-100 比例数 0.05 0.15 0.40 0.30 0.10 11/19/2018

A<60 N Y A<70 不及格 N Y 及格 A<80 N Y A<90 中等 N Y 良好 优秀 11/19/2018

70≤A<80 N Y 80≤A<90 中等 N Y 良好 60≤A<70 N Y A<60 及格 N Y 不及格 优秀 11/19/2018

A<80 N Y A<70 A<90 N Y Y N 中等 良好 优秀 A<60 N Y 及格 不及格 10000个输入,各需要多少次比较 11/19/2018

归并排序 练习23 11/19/2018

11/19/2018