堆排序算法-(28734)

《堆排序算法-(28734)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、---堆排序算法二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性：1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。堆的存储一般都用数组来表示堆，i结点的父结点下标就为(i–1)/2。它------的左右子结点下标分别为2*i+1和2*i+2。------堆的插入------每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数

2、列，现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中.堆的删除按定义，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一------次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程堆化数组有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如intA[]={9,12,17,30,50,

3、20,60,65,4,49};很明显，对叶子结点来说，可以认为它已经是一个合法的堆了即20，60，65，4，49都分别是一个合法的堆。只要从A[4]=50开始向下调整就可以了。然后再取A[3]=30，A[2]=17，A[1]=12，A[0]=9分别作一次向下调整操作就可以了堆排序首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据，重复上述步骤直至堆中只有一个数据时就直接取出这个数据。由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n-1]交换，再对A[0⋯n-2]重新恢复堆。第二次将A[0]与A[n–2]

4、交换，再对A[0⋯n-3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了------由于每次重新恢复堆的时间复杂度为O(logN)，共N-1次重新恢复堆操作，再加上前面建立堆时N/2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N*logN)。故堆排序的时间复杂度为O(N*logN)#define_CRT_SECURE_NO_WARNINGS#include#include#include#include

5、>#defineMAXSIZE1000000//交换值voidSwap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}//打印数组元素voidPrintArr(int*arr,intlength){for(inti=0;i

6、,intindex,intlength){intlchild=2*index+1;------intrchild=2*index+2;intmax=index;if(lchildarr[max]){max=lchild;}if(rchildarr[max]){max=rchild;}if(max!=index){Swap(&arr[max],&arr[index]);BigHeadAdjust(arr,max,length);}return;}//堆排序，采用大顶堆升序voidHeapSort_Up(int

7、*arr,intlength){//初始化堆，将每个非叶子结点倒叙进行大顶堆调整。//循环完毕初始大顶堆（每个根结点都比它孩子结点值大）形成for(inti=length/2-1;i>=0;i--){BigHeadAdjust(arr,i,length);}//printf("大堆顶初始化顺序：");//PrintArr(arr,length);//将堆顶值放到数组尾部，然后又进行大堆顶调整，一次堆调整最值就到堆顶了。f