[编程珠玑读书笔记]堆排序，小根堆

堆排序的关键是要实现siftup和siftdown。当建立完这两个函数以后，排序一个数组只需要5行代码。算法执行了n-1次siftup和siftdown，而每次操作的成本最多O(lgn)，所以运行时间为O(nlogn)。

#include <stdio.h>
#include <stdlib.h>


#define MAX 20


void swap( int *data, int i, int j)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}


//siftup比较好理解，将每一个元素都与自己的父亲比较，如果自己的值小于父亲的值，就互换，直到到堆顶，或父亲的值小于自己的值为止。
void siftup(int *data, int n )
{
int i = n;
int p;
while( 1 )
{
if ( i == 1 ) break;
p = i/2;
if( data[p] <= data[i]) break;
swap( data, i, p );
i = p;
}
}


//这里的n其实意义不大，是指n之后的数据是符合要求的，n之前的数据可能不满足小根堆的要求，调整的方法也是从堆顶开始，初步向小调整
void siftdown( int *data, int n)
{
int i = 1;
int c = 0;
while( 1 )
{
c = 2 * i;
if( c > n ) break;
//取两个孩子中较小的一个与自己作比较
if( c + 1 <= n && data[ c + 1] < data[c] )
c++;


//如果孩子的值小于自己的值，则互换
if( data[i] <= data[c] )
break;
swap( data, c, i);
i = c;
}
}


int main()
{
int data[ MAX + 1];
int i= 0;
srand(5);
for( i = 1; i <= MAX; i++ )
data[i] = rand() % 500;


//建堆
for( i = 2; i <= MAX; i++ )
siftup(data,i);


//从后向前调整
for( i =MAX; i >= 2; i--)
{
swap(data, 1, i);
siftdown(data, i - 1 );
}


for( i = 1; i < MAX; i++ )
printf("%d\t", data[i]);


printf("\n");
return 0;
}

堆排序与系统排序的效率比较：

#include <stdio.h>
#include<iostream>
#include<string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;

#define MAX 200000

void swap( int *data, int i, int j)
{
	int temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

//siftup比较好理解，将每一个元素都与自己的父亲比较，如果自己的值小于父亲的值，就互换，直到到堆顶，或父亲的值小于自己的值为止。
void siftup(int *data, int n )
{
	int i = n;
	int p;
	while( 1 )
	{
		if ( i == 1 ) break;
		p = i/2;
		if( data[p] <= data[i]) break;
		swap( data, i, p );
		i = p;
	}
}

//这里的n其实意义不大，是指n之后的数据是符合要求的，n之前的数据可能不满足小根堆的要求，调整的方法也是从堆顶开始，初步向小调整
void siftdown( int *data, int n)
{
	int i = 1;
	int c = 0;
	while( 1 )
	{
		c = 2 * i;
		if( c > n ) break;
		//取两个孩子中较小的一个与自己作比较
		if( c + 1 <= n && data[ c + 1] < data[c] )
			c++;

		//如果孩子的值小于自己的值，则互换
		if( data[i] <= data[c] )
			break;
		swap( data, c, i);
		i = c;
	}
}

int main()
{
	double BegTime, EndTime;
	int data[ MAX + 1];
	int data2[ MAX + 1];
	data2[0] = 0;
	int i= 0;
	srand(5);
	for( i = 1; i <= MAX; i++ )
		data[i] = rand() % 500;

	memcpy( data2, data, MAX+1);
	BegTime = clock();
	//建堆
	for( i = 2; i <= MAX; i++ )
		siftup(data,i);

	//从后向前调整
	for( i =MAX; i >= 2; i--)
	{
		swap(data, 1, i);
		siftdown(data, i - 1 );
	}
	EndTime = clock();
	printf("HeapSort:%gms\n", (EndTime - BegTime) / 1000);

	BegTime = clock();
	sort(data2, data2 + MAX + 1);
	EndTime = clock();
	printf("sort: %gms\n", (EndTime - BegTime) / 1000);


	printf("\n");
	return 0;
}

测试结果如下：

HeapSort:60ms
sort: 40ms

结果表明，堆排序确实有着相当不错的表现，不到必须的时候，还是应当使用系统的sort函数，效率很高，且节约开发成本。