图解堆排序Heap Sort算法.docx

《图解堆排序Heap Sort算法.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、在程序设计相关领域，堆(Heap)的概念主要涉及到两个方面：一种数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。垃圾收集存储区，是软件系统可以编程的内存区域。本文所说的堆，指的是前者。堆排序的时间复杂度是O(nlgN)，与快速排序达到相同的时间复杂度。但是在实际应用中，我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现，往往比堆排序具有更好的表现。堆排序的主要用途，是在形成和处理优先级队列方面。另外，如果计算要求是类优先级队列（比如，只要返回最大或者最小元素，只有有限的插入要求等），堆同样是很适合的数据结构。基础

2、知识堆一般用数组表示，比如数组A数组的长度Length(A)，堆在数组中的元素个数HeapSize(A)。一般说来，HeapSize(A)<=Length(A)，因为数组A当中可能有一些元素不在堆中。假设节点I是数组A中下标为i的节点。Parent(i):returnFloor(i/2);//I的父节点下标，Floor(i)表示比i小的最大整数。Left(i):return2*i;//I的左子节点Right(i):return2*i+1;//I的右子节点含有n个元素的堆A的高度是:Floor(lgn)。堆的基本操作MaxHeapify(A,i)

3、:保持堆的性质。假设数组A和下标i，假定以Left(i)和Right(i)为根结点的左右两棵子树都已经是最大堆，节点i的值可能小于其子节点。调整节点i的位置。BuildMaxHeap(A):从一个给定的数组建立最大堆。子数组A[floor(n/2)+1.......n]中的元素都是树的叶节点(完全二叉树的基本性质)。从索引ceiling(n/2)开始一直到1，对每一个元素都执行MaxHeapify，最终得到一个最大堆。堆排序HeapSort(A):堆排序算法的基本思想是，将数组A创建为一个最大堆，然后交换堆的根(最大元素)和最后一个叶节点x，将

4、x从堆中去掉形成新的堆A1，然后重复以上动作，直到堆中只有一个节点。优先级队列算法-增加某元素的值(优先级):HeapIncreaseKey(A,i,key)增加某一个元素的优先级后（元素的值），该元素应该向上移动，才能保持堆的性质。优先级队列算法-插入一个元素:Insert(S,x)将x元素插入到优先级队列S中。主要思路是，将堆的最后一个叶节点之后，扩展一个为无穷小的新叶节点，然后增大它的值为x的值。堆排序实现原理堆排序的C语言实现01#include02#include03voidHeapSort(in

5、tnum[],intsize);04voidBuildHeap(intnum[],intsize);05voidPercolateDown(intnum[],intindex,intsize);06voidPrintHeap(constchar*strMsg,intarray[],intnLength);07voidSwap(intnum[],intv,intu);08intmain(intargc,char*argv[])09{10intdata[13]={8,5,4,6,13,7,1,9,12,11,3,10,2};11HeapSort(d

6、ata,13);1213system("PAUSE");14return0;15}16voidHeapSort(intnum[],intsize)17{18inti;19intiLength=size;2021PrintHeap("BeforSort:",num,iLength);2223BuildHeap(num,size);//建立小顶堆2425for(i=iLength-1;i>=1;i--){26Swap(num,0,i);//交换27size--;//每交换一次让规模减少一次28PercolateDown(num,0,size);//

7、将新的首元素下滤操作29PrintHeap("SortHeap:",num,iLength);30}31}32//建堆方法，只需线性时间建好33voidBuildHeap(intnum[],intsize){34inti;35for(i=size/2-1;i>=0;i--){//对前一半的节点（解释为“从最后一个非叶子节点开始，将每个父节点都调整为最小堆”更合理一些）36PercolateDown(num,i,size);//进行下滤操作37PrintHeap("Buildheap:",num,size);38}39}4041//对该数进行下滤

8、操作，直到该数比左右节点都小就停止下滤42voidPercolateDown(intnum[],intindex,intsize){43intmin;