算法设计与分析-6堆排序VIP免费

算法设计与分析谭守标安徽大学电子学院2007.9第五章堆排序堆的基本概念和性质堆的基本操作（过程及分析）堆排序算法（过程及分析）堆排序应用—优先级队列（过程及分析）程序展示和讲解一、堆的基本概念和性质1、定义：堆可看作为一完全二叉树，大根堆的任一非终端节点（叶子节点）的数据不小于其子节点的数据。2、两个特点：①根节点上为该堆的最大元素。②较大的数据位于较低的层次。堆的属性1、length[A]：数组中的元素个数2、heapsize[A]:存放在A中的堆的元素个数显然heapsize[A]≤length[A]3、给定一个节点的下标i，其父节点为┖i/2┚，其左儿子[LEFT(i)]为2i、右儿子[RIGHT(i)]为2i+1.五个基本过程1、HEAPIFY过程:维持堆性质，运行时间O(lgn).2、BUILD--HEAP过程：从无序的输入数组中构造出一个堆来，运行时间O(n).3、HEAPSORT过程：对一个数组进行排序，运行时间O(nlgn).4、EXTRACT--MAX和INSERT过程：是堆结构可以作为一个优先级队列来用，运行时间O(lgn).堆实例二、堆的基本操作HEAPIFY过程1、过程说明：对于第i个数，假定以它左儿子[LEFT(i)]和右儿子[RIGHT(i)]为根的两棵子树都已为堆，调用HEAPIFY使得以i为根的子树成为一个的堆。2、过程图例3、算法如下1、l←LEFT(i)2、r←RIGHT(i)3、ifl≤heapsize(A)andA[l]>A[i]4、thenlargest←l5、elselargest←i6、ifr≤heapsize(A)andA[r]>A[largest]7、thenlargest←r8、iflargest≠i9、thenexchangeA[i]←→A[largest]10、HEAPIFY(A,largest)4、运行时间①T(n)=T(2/3n)+Θ（1）可得T(n)=O（lgn)②因为堆的高度最大为lgn所以可知T(n)=O（lgn)BUILD-HEAP过程1、图例2、BUILD-HEAP(A)算法1)heapsize[A]←length[A]2)fori←┖length[A]/2┚downto13)doHEAPIFY(A,i)3、运行时间粗估：每调一次HEAPIFY(A,i)的时间为O（lgn)，总共有O（n)次调用，故运行时间最多为O（nlgn).此时间是不紧确的。紧确估计：含n个元素的堆中至多有个节点的高度为h21hn三、堆排序算法1、图例：2、算法1)BUILDHEAP(A)2)fori←length[A]downto23)doexchangeA[1]←→A[i]4)heapsize(A)←→heapsize(A)-15)HEAPIFY(A,1)3、运行时间堆排序的时间建堆的时间为O(n)+（n-1)次的HEAPIFY调用时间O(lgn)，所以总的代价为O(nlgn)四、优先级队列一、常见操作1、INSERT(S,x):把元素x插入集合S.可记为S←S∪{x}.2、MAXIMUM(S):返回S中具有最大关键字的元素。3、EXTRACT—MAX(S):去掉并返回S中具有最大关键字的元素。HEAP-EXTRACT-MAX过程HEAP—EXTRACT—MAX(A)1.ifheap—size[A]<12.thenerror“heapunderflow”3.max←A[1]4.A[1]←A[heap—size[A]]5.heap—size[A]←heap—size[A]-16.HEAPIFY(A,1)7.returnmaxHEAP-EXTRACT-MAX过程运行时间从算法中可以看出该过程的运行时间为O(lgn)。INSERT(S,x)过程1、图例2、HEAP—INSERT(A,key)算法1、heap—size[A]←heap—size[A]+12、i←heap—size[A]3、whilei>1andA[PARENT(i)]