数据结构、算法及其应用.pptx

数据结构、算法与应用C++描述;堆(Heaps) 左高树(Leftist Trees);Focus;与FIFO结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序。 例-CPU调度;优先队列是0个或多个元素的集合，每个元素都有一个优先权或值。 对优先队列执行的操作有： 查找 插入一个新元素 删除;描述最大优先队列最简单的方法是采用无序线性表。 假设有一个具有n个元素的优先队列，插入操作可以十分容易地在表的右端末尾执行，插入所需时间为Θ(1)。删除操作时必须查找优先权最大的元素，即在未排序的n个元素中查找具有最大优先权的元素，所以删除操作所需时间为Θ(n)。;如果利用链表，插入操作在链头执行，时间为Θ(1)，而每个删除操作所需时间为Θ(n)。;另一种描述方法是采用有序线性表，当使用公式化描述时元素按递增次序排列，使用链表时则按递减次序排列，这两种描述方法的删除时间均为Θ(1)，插入操作所需时间为Θ(n)。;定义：每个节点的值都大于或等于其子节点（如果有的话）值的树。;最大树;定义：每个节点的值都小于或等于其子节点（如果有的话）值的树。;最小树;定义：最大（最小）的完全二叉树。;最大堆的插入;插入时间复杂性;最大堆的删除;最大堆的删除;删除时间复杂性;开始时堆中已经含有n(n0) 个元素。可以通过在初始为空的堆中执行n次插入操作来构建非空的堆，插入操作所需总时间为O(nlogn) 。;更快的堆的初始化策略？;从第一个具有孩子的节点开始，这个元素在数组中的位置为i=[n/2]，如果以这个元素为根的子树已是最大堆，则此时不需调整，否则必须调整子树使之成为堆。 随后，继续检查以i-1,i-2等节点为根的子树，直到检查到整个二叉树的根节点（其位置为1）。;最大堆的初始化;最大堆的初始化;类MaxHeap;最大堆的插入;最大堆的删除;最大堆的删除;一棵二叉树，它有一类特殊的节点叫做外部节点(external node)，用来代替树中的空子树，其余节点叫做内部节点(internal node)。 增加了外部节点的二叉树被称为扩充二叉树(extended binary tree)。;堆结构是一种隐式数据结构，用完全二叉树表示的堆在数组中是隐式存贮的。由于没有存贮结构信息，这种描述方法空间利用率很高。 尽管堆结构的时间和空间效率都很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用，左高树就能满足这种要求。;扩充二叉树;令s(x)为从节点x到它的子树的外部节点的所有路径中最短的一条，根据s(x)的定义可知，若x是外部节点，则s的值为0，若x为内部节点，则它的s值是： min{s(L),s(R)} + 1 其中L与R分别为x 的左右孩子。;扩充二叉树的s和w;定义：当且仅当一棵二叉树的任何一个内部节点，其左孩子的 s 值大于等于右孩子的 s 值时，该二叉树为高度优先左高树（height-biased leftist tree, HBLT）。;定理9-1 令x为一个HBLT的内部节点，则 以x为根的子树的节点数目至少为2s(x)-1。 若子树x有m个节点，s(x)最多为log2(m+1)。 通过最右路径（即，此路径是从x 开始沿右孩子移动）从x到达外部节点的路径长度为s(x)。;[最大HBLT] 即同时又是最大树的HBLT； [最小HBLT] 即同时又是最小树的HBLT。;插入 删除 合并 初始化;最大HBLT的插入操作可借助于最大HBLT的合并操作来完成。 假设将元素x插入到名为H的最大HBLT中，如果建造一棵仅有一个元素x的最大HBLT然后将它与H进行合并，结果得到的最大HBLT将包括H中的全部元素及元素x。因此插入操作只需先建立一棵仅包含欲插入元素的HBLT，然后将它与原来的HBLT合并即可。;根是最大元素，如果根被删除，将留下分别以其左右孩子为根的两棵HBLT的子树。将这两棵最大HBLT合并到一起，便得到包含除删除元素外所有元素的最大HBLT。 所以删除操作可以通过删除根元素并对两个子树进行合并来实现。;具有n个元素的最大HBLT，其最右路径的长度为O(logn)。合并操作仅需遍历欲合并的HBLT的最右路径。由于在两条最右路径的每个节点上只需耗时O(1)，因此将两棵HBLT进行合并具有对数复杂性。 通过以上观察，在合并算法中，仅需移动右孩子。;合并策略最好用递归来实现。 令A、B为需要合并的两棵最大HBLT，如果其中一个为空，则将另一个作为合并的结果，因此可以假设两者均不为空。 为实现合并，先比较两个根元素，较大者作为合并后的HBLT的根。假定A具有较大的根，且其左子树为L