堆与堆排序PPT课件.ppt

堆与堆排序☞一、堆和堆排序的概念二、堆的调整三、建堆四、堆排序堆的定义：若n个元素的序列{a1a2…an}满足ai≤a2i或ai≥a2iai≤a2i+1ai≥a2i+1则分别称该序列{a1a2…an}为小根堆和大根堆。从堆的定义可以看出，堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于(大于)它的孩子结点例:下面序列为堆，对应的完全二叉树分别为:堆的应用------优先级队列堆排序若在输出堆顶的最小值（最大值）后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值）……如此反复，便能得到一个有序序列，这个过程称之为堆排序。实现堆排序需解决两个问题：1、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素后，调整剩余元素为一个新的堆？下面先讨论第二个问题：一、堆和堆排序的概念☞二、堆的调整三、建堆四、堆排序如何在输出堆顶元素后，调整剩余元素为一个新的堆？解决方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”13堆调整与数组变化的关系加入元素AddinganEntryAddinganEntryAddinganEntryAddinganEntryAddinganEntry----代码见课本203删除元素RemovingtheRoot一、堆和堆排序的概念二、堆的调整☞三、建堆四、堆排序第一种方法：创建堆时间复杂度可以看出：对一个无序序列反复“筛选”就可以得到一个堆即：从一个无序序列建堆的过程就是一个反复“筛选”的过程。那么：怎样判断一个序列是一个堆？或者说，建堆操作从哪儿着手？显然：单结点的二叉树是堆；在完全二叉树中所有以叶子结点（序号i>n/2）为根的子树是堆。这样，我们只需依次将以序号为n/2，n/2－1，……,1的结点为根的子树均调整为堆即可。即：对应由n个元素组成的无序序列，“筛选”只需从第n/2个元素开始。由于堆实质上是一个完全二叉树，那么我们可以顺序存储一个堆。下面以一个实例介绍建一个小根堆的过程。例：有关键字为49，38，65，97，76，13，27，49的一组记录，将其按关键字调整为一个小根堆。49筛选过程的算法描述为：sift(rectypeR[],inti,intm)//在数组R中将下标从i到m的元素序列调整为堆，即将以R[i]为根的子树调整为堆；初次调整的是以序号m/2的结点为根的子树；{intj;j=2*i;while(j<=m)//若j<=m，R[2*i]是R[i]的左孩子{if(j<m&&R[j].key>R[j+1].key)j++;//比较左右孩子的大小，使j为较小的孩子的下标if(R[i].key>R[j].key){R[i]<－>R[j];//将较小的孩子与根交换i=j;j=2*i;//上述交换可能使以该孩子结点为根的子树不再为堆，则需重新调整}elsebreak;}}将初始无序的R[1]到R[n]建成一个小根堆，可用以下语句实现：for(i=n/2;i>=1;i--)sift(R,i,n);自底向上地创建堆Example(contd.)Example(contd.)Example(end)Analysis时间复杂度分析一、堆和堆排序的概念二、堆的调整三、建堆☞四、堆排序HeapsortHeapsortHeapsortHeapsort由以上分析知：若对一个无序序列建堆，然后输出根；重复该过程就可以由一个无需序列输出有序序列。实质上，堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。堆排序算法如下：HeapSort(rectypeR[])//对R[1]到R[n]进行堆排序{inti;rectypetemp;for(i=n/2;i>=1;i--)sift(R,i,n);//建初始堆for(i=n;i>1;i--)//进行n－1趟排序{temp=R[1];R[1]=R[i];R[i]=temp;//根与最后一个元素交换sift(R,1,i-1)//对R[1]到R[i-1]重新建堆}}堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。堆排序在最坏情况下，其时间复杂度也为O(nlog2n)，这是堆排序的最大优点。另外，堆排序仅需一个记录大小供交换用的辅助存储空间。然而堆排序是一种不稳定的排序方法，它不适用于待排序记录个数n较少的情况，但对于n较大的文件还是很有效的。HeapsortHeapsort