学步园

以前写过一个堆排序，但是实话实说，根本不知所云。

今天看了算法导论 关于堆排序的讲解，就实现了一下。

在《算法导论》中关于堆排序的描述是：像合并排序而不像插入排序，运行时间为O（n*logn）。
是一种原地排序算法：在任何时间只有常数个数据在数组外面。

堆排序操作的重要伪代码：

1：保持堆的性质；
MAX-HEAPIFY(A，i)
1 l <- LEFT(i)
2 r <- RIGHT(i)
3 if l<=heap-size(A) and A[l] > A[i]
4     then largest <- l
5     else largest <- i
6 if r<=heap-size(A) and A[r] > A[i]
7    then largest <- r
8 if largest != i
9        then exchange A[i]<->A[largest]
10 MAX-HEAPIFY(A,largest)

2:建堆
BUILD-MAX-HEAP(A)
1  heap-size[A] <- length[A]
2  for i <- length[A]/2 downto 1
3        do MAX-HEAPIFY(A,i)

3:排序
HEAP-SORT(A)
1 BUILD-MAX-HEAP(A)
2 for i <- length[A] downto 2
3    do exchange A[1] <-> A[i]
4        heap-size[A] <- heap-size[A]-1
5        MAX-HEAPIFY(A,1)

算法导论中讲解的是最大堆，我实现的是最小堆，其实两者的操作区别不大：

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
int length;

int parent(int i)
{
	return i/2;
}
int left(int i)
{
	return 2*i;
}
int right(i)
{
	return 2*i+1;
}


void swap(int *group,int i,int k)
{
	int temp;
	temp = group[i];
	group[i]=group[k];
	group[k]=temp;
}

//调整堆
void heap_adjust(int group[],int i)
{
	int l,r,smallest;
	l = left(i);
	r = right(i);

	if(l<=length && group[l]<group[i])
		smallest = l;
	else
		smallest = i;

	if(r<=length && group[r]<group[smallest])
		smallest = r;
	if(smallest != i)
	swap(group,i,smallest);
}

//建立一个堆
void build_heap(int group[])
{
	int i;
	for(i=length/2;i>=1;i--)
	{
		heap_adjust(group,i);
	}
}

//输出堆中最小的元素
int heap_min(int group[])
{
	int min;
	if(length<1)return FALSE;
	min = group[1];
	group[1]=group[length];
	length-=1;
	heap_adjust(group,1);
	return min;
}

//增加堆中某一元素的数值，注意是增加
void heap_increase(int group[],int i,int key)
{
	if(key < group[i])return ;
	else
	{
		group[i]=key;
		while(i>1&&group[parent(i)]<group[i])
		{
			swap(group,i,parent(i));
			i=parent(i);
		}
	}
}

//向堆中添加元素
void heap_insert(int group[],int key)
{
	length += 1;
	group[length] = -999999;
	heap_increase(group,length,key);
}

//堆排序
void heap_sort(int *group)
{
	int i;
	build_heap(group);
	for(i=length;i>=2;i--)
	{
		swap(group,1,i);
		length--;
		heap_adjust(group,1);
	}
}
int main()
{
	int *group;
	int i,n;
	scanf("%d",&n);
	group = (int*)malloc(sizeof(int)*(2*n+1));
	for(i=1;i<=n;i++)
		scanf("%d",group+i);
	length = n;
	heap_sort(group);
	for(i=1;i<=n;i++)
		printf("%d ",*(group+i));
	return 0;
}