疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

堆排序解析


 

一、堆的定义
       是n个元素的序列H={k1, k2 , … kn},满足ki≤k2i      当2i≤n时       ki≥k2i       当2i≤n时或者 
ki≤k2i+1   当2i+1≤n时 
ki ≥k2i+1    当2i+1≤n时  
由堆的定义知,堆是一棵以k1为根的完全二叉树。若对该二叉树的结点进行编号(从上到下,从左到右),得到的序列就是将二叉树的结点以顺序结构存放,堆的结构正好和该序列结构完全一致。
二、  堆的性质
①  堆是一棵采用顺序存储结构的完全二叉树, k1是根结点;
②  堆的根结点是关键字序列中的最小(或最大)值,分别称为小(或大)根堆;
③  从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的;
④堆中的任一子树也是堆。
        利用堆顶记录的关键字值最小(或最大)的性质,从当前待排序的记录中依次选取关键字最小(或最大)的记录,就可以实现对数据记录的排序,这种排序方法称为堆排序。
三、  堆排序思想
①  对一组待排序的记录,按堆的定义建立堆;
②  将堆顶记录和最后一个记录交换位置,则前n-1个记录是无序的,而最后一个记录是有序的;
③  堆顶记录被交换后,前n-1个记录不再是堆,需将前n-1个待排序记录重新组织成为一个堆,然后将堆顶记录和倒数第二个记录交换位置,即将整个序列中次小关键字值的记录调整(排除)出无序区;
④  重复上述步骤,直到全部记录排好序为止。
 结论:排序过程中,若采用小根堆,排序后得到的是非递减序列;若采用大根堆,排序后得到的是非递增序列。
堆排序的关键
①  如何由一个无序序列建成一个堆?
②  如何在输出堆顶元素之后,调整剩余元素,使之成为一个新的堆?
四、堆调整
 输出堆顶元素之后,以堆中最后一个元素替代之;然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;重复上述操作,直到是叶子结点或其关键字值小于等于左、右子树的关键字的值,将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选
堆调整算法实现
[cpp] view plaincopy
<span style="font-size:24px;">void Heap_adjust(Sqlist *H, int s, int m)  
/*  H->R[s…m]中记录关键字除H->R[s].key均满足堆定义  */  
/*  调整H->R[s]的位置使之成为小根堆  */  
{  int j=s, k=2*j ;     /*  计算H->R[j]的左孩子的位置  */  
H->R[0]=H->R[j] ;       /*  临时保存H->R[j]  */   
for (k=2*j; k<=m; k=2*k)  
{  if ((k<m)&&(LT(H->R[k+1].key, H->R[k].key))   
    k++ ;      /*  选择左、右孩子中关键字的最小者  */  
if  ( LT(H->R[k].key, H->R[0].key) )  
    {   H->R[j]=H->R[k] ; j=k ; k=2*j  }  
else  break ;  
}  
H->R[j]=H->R[0] ;   
}  
</span>  
五、堆的建立
利用筛选算法,可以将任意无序的记录序列建成一个堆,设R[1],R[2], …,R[n]是待排序的记录序列。
       将二叉树的每棵子树都筛选成为堆。只有根结点的树是堆。第⌊n/2⌋个结点之后的所有结点都没有子树,即以第ën/2û个结点之后的结点为根的子树都是堆。因此,以这些结点为左、右孩子的结点,其左、右子树都是堆,则进行一次筛选就可以成为堆。同理,只要将这些结点的直接父结点进行一次筛选就可以成为堆…。
       只需从第ën/2û个记录到第1个记录依次进行筛选就可以建立堆。
可用下列语句实现:
for (j=n/2; j>=1; j--)
Heap_adjust(R, j , n) ;
六、堆排序实现
堆的根结点是关键字最小的记录,输出根结点后,是以序列的最后一个记录作为根结点,而原来堆的左、右子树都是堆,则进行一次筛选就可以成为堆。
[cpp] view plaincopy
<span style="font-size:24px;">void  Heap_Sort(Sqlist *H)  
{  int j ;  
for (j=H->length/2; j>0; j--)  
Heap_adjust(H, j , H->length) ;   /*   初始建堆   */  
for (j=H->length/2; j>=1; j--)  
{  H->R[0]=H->R[1] ; H->R[1]=H->R[j] ;  
H->R[j]=H->R[0] ;   /*   堆顶与最后一个交换   */  
Heap_adjust(H, 1, j-1) ;   
}  
}  
</span>  
 
七、算法分析
主要过程:初始建堆和重新调整成堆。设记录数为n,所对应的完全二叉树深度为h 。
◆  初始建堆:每个非叶子结点都要从上到下做“筛选”。第i层结点数≤2i-1,结点下移的最大深度是h-i,而每下移一层要比较2次,则比较次数C1(n)为:

堆排序的比较次数的数量级为:T(n)=O(n㏒2n);而附加空间就是交换时所用的临时空间,故空间复杂度为:S(n)=O(1) 。