堆和堆排序 (二)

实现代码：

[cpp]
template
void BinaryHeap::buildHeap()
{
for(int i=theSize/2;i>0;--i)
percolateDown(i);
}

template
void BinaryHeap::buildHeap()
{
for(int i=theSize/2;i>0;--i)
percolateDown(i);
}
点击此处查看最小堆类模板完整源代码

堆排序
顾名思义，堆排序是利用堆的特性来对一组数据进行排序。堆排序可分为以下个步骤（从小到大排序）：

对所有n个数据进行建堆（最大堆）操作。
将堆顶元素和堆尾元素交换，对剩下的n-1个数据进行建堆（最大堆）操作。
重复步骤2直至堆的大小为1，此时数据完成排序。
有两个问题需要重视：

被排序的数据从0开始索引，所以父亲和孩子的位置都有了相应的变化。父亲的位置由i/2变为(i-1)/2，左孩子的位置由2i变为2i+1，右孩子的位置由2i+1变为2i+2。
下滤操作需要知道当前堆的大小。

实现代码：

[cpp]
template
void percolateDown(vector& vec,int i,int length)
{
int child;
T temp = vec[i];
for(;2*i+1<=length-1;i=child)
{
child = 2*i+1;
if(childtemp)
vec[i] = vec[child];
else
break;
}
vec[i] = temp;
}

template
void heapSort(vector& vec)
{
for(int i = vec.size()/2;i>=0;--i)
percolateDown(vec,i,vec.size());
for (int j = vec.size()-1;j!=0;--j)
{
swap(vec[0],vec[j]);
percolateDown(vec,0,j);
}
}

void main()
{
int a[]={312,33,44,5,6,4,2,3,4,5,6,76,8,6,88768,5345,43,432};
vector vec(a,a+sizeof(a)/sizeof(*a));
for (int i=0;i!=vec.size();++i)
cout< cout< heapSort(vec);
for (int i=0;i!=vec.size();++i)
cout< cout< }

template
void percolateDown(vector& vec,int i,int length)
{
int child;
T temp = vec[i];
for(;2*i+1<=length-1;i=child)
{
child = 2*i+1;
if(childtemp)
vec[i] = vec[child];
else
break;
}
vec[i] = temp;
}

template
void heapSort(vector& vec)
{
for(int i = vec.size()/2;i>=0;--i)
percolateDown(vec,i,vec.size());
for (int j = vec.size()-1;j!=0;--j)
{
swap(vec[0],vec[j]);
percolateDown(vec,0,j);
}
}

void main()
{
int a[]={312,33,44,5,6,4,2,3,4,5,6,76,8,6,88768,5345,43,432};
vector vec(a,a+sizeof(a)/sizeof(*a));
for (int i=0;i!=vec.size();++i)
cout< cout< heapSort(vec);
for (int i=0;i!=vec.size();++i)
cout< cout< }
在PercolateDown算法中，在每一个阶段中考虑的项的数目是前一阶段的一半。因此，与二叉查找树的情况类似，这个算法的最坏计算时间是O(logn)。由于BuildHeap操作执行了n/2次PercolateDown操作，其最坏计算时间是O(nlogn)。HeapSort执行一次BuildHeap操作和n-1次PercolateDown操作，因此其最坏计算时间是O(nlogn)。