赞
踩
堆的概念:
本质是一种数组对象。特别重要的一点性质:任意的叶子节点小于(或大于)它所有的父节点。对此,又分为大顶堆和小顶堆,大顶堆要求节点的元素都要大于其孩子,小顶堆要求节点元素都小于其左右孩子,两者对左右孩子的大小关系不做任何要求。利用堆排序,就是基于大顶堆或者小顶堆的一种排序方法。下面,我们通过大顶堆来实现。
基本思想:
即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。
第三步: 重新调整堆。此时3位于堆顶不满堆的性质,则需调整继续调整(从顶点开始往下调整)
重复上面的步骤:
//调整堆
void HeapAdjust(int a[],int s,int m)//一次筛选的过程
{
int rc,j;
rc=a[s];
for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选
{
if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标
if(rc>a[j]) break;
a[s]=a[j];s=j;
}
a[s]=rc;//插入
}
void HeapSort(int a[],int n)
{
int temp,i,j;
for(i=n/2;i>0;i--)//通过循环初始化顶堆
{
HeapAdjust(a,i,n);
}
for(i=n;i>0;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;//将堆顶记录与未排序的最后一个记录交换
HeapAdjust(a,1,i-1);//重新调整为顶堆
}
}
空间复杂度:堆排序数据交换时需要一个辅助空间,故空间复杂度是O(1)
在构建堆(初始化大顶堆)的过程中,完全二叉树从最下层最右边的非终端结点开始构建,将它与其孩子进行比较和必要的互换,对于每个非终端结点来说,其实最多进行两次比较和一次互换操作,因此整个构建堆的时间复杂度为: O(n)。大概需进行n/2 * 2 = n次比较和n/2次交换。
在正式排序时,n个结点的完全二叉树的深度为⌊log2n⌋+1,并且有n个数据则需要取n-1次调整成大顶堆的操作,每次调整成大顶堆的时间复杂度为O(log2n)。因此,重建堆的时间复杂度可近似看做: O(nlogn)。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。