《算法之美》---堆排序

堆可分为大根堆和小根堆；对小根堆来说，若在输出堆顶的最小值后，使得剩余的n-1个元素的序列重又建成一个小根堆，则得到n个元素中的次小值。如此反复执行，便能得到一个有序序列，这个过程称为堆排序。堆排序只需要一个用来记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。

从一个无序序列建立堆的过程就是一个反复“筛选”的过程，若将此序列看成是一个完全二叉树，则最后一个非终端节点是第(n-1)/2+1个元素，由此“筛选”只需从第(n-1)/2+1个元素开始。

为了使记录序列按关键字非递减有序排列，则在堆排序的算法中先建立一个“大根堆”，即先选得一个关键字为最大的记录并与序列中的最后一个记录交换，然后对序列中前n-1个记录进行筛选，重新将它调整为一个“大根堆”，如此反复直至排序结束。由此，“筛选”应沿关键字较大的孩子节点向下进行。

堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建立初始堆和调整建立新堆时进行的反复“筛选”上。堆排序在最坏情况下，时间复杂度为O(nlogn)，相对于快速排序来说，这是堆排序的最大优点。

堆排序代码模板如下：

/*

函数名： heap_down

功能： 堆排序辅助过程

*/

template <typename T>

void heap_down (T data[], int i, const int& size)

{

int p=i*2+1;

while ( p<size ) //i的左孩子存在

{

if ( p+1<size ) //i的右孩子存在

{

if ( data[p]<data[p+1] ) //沿关键字较大的孩子节点向下筛选

++p;

}

if ( data[i]<data[p] )

{

std::swap(data[p], data[i]);

i=p;

p=i*2+1;

}

else

break;

}

}

/*

函数名： HeapSort

功能： 堆排序

模板参数说明：T必须支持小于操作

参数说明： data待排序数组, size待排序数组大小

前置条件： data!=NULL, size>0

后置条件： data按非降序排列

用法：

#include <algorithm>

int arr[]={10,9,8,4,5,7,6,3,1,4};

HeapSort(arr, 10);

*/

template <typename T>

void HeapSort (T data[], int size)

{

int i;

//把data[0…size-1]建成大根堆

for (i=(size-1)/2; i>=0; --i)

heap_down(data, i, size);

for (i=size-1; i>0; --i)

{

std::swap(data[0], data[i]); //将堆顶记录data[0]和当前未经排序子序列data[1…i]中

//最后一个记录data[i]相互交换

heap_down(data, 0, i); //将数组data[0, i-1]重新调整为大根堆

}

}

/*

函数名： heap_down

功能： 堆排序辅助过程

*/

template <typename T, typename Func>

void heap_down (T data[], int i, const int& size, Func& f)

{

int p=i*2+1;

while ( p<size )

{

if ( p+1<size )

{

if ( f(data[p],data[p+1]) )

++p;

}

if ( f(data[i],data[p]) )

{

std::swap(data[p], data[i]);

i=p;

p=i*2+1;

}

else

break;

}

}

/*

函数名： HeapSort

功能： 堆排序

模板参数说明：T元素类型, Func函数对象或指针

参数说明： data待排序数组, size待排序数组大小,函数对象或指针

前置条件： data!=NULL, size>0

后置条件： data按排列

用法：

#include <algorithm>

bool cmp(int a, int b)

{ return a<b; }

int arr[]={10,9,8,4,5,7,6,3,1,4};

HeapSort(arr, 10，cmp);

*/

template <typename T, typename Func>

void HeapSort (T data[], int size, Func f)

{

int i;

for (i=(size-1)/2; i>=0; --i)

heap_down(data, i, size, f);

for (i=size-1; i>0; --i)

{

std::swap(data[0], data[i]);

heap_down(data, 0, i, f);

}

}