heap.h

快速排序、合并排序、插入排序、堆排序、计数排序等算法的C语言实现

#include<stdio.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define FLAG -1
//堆排序头文件
//一个堆可以看作一棵完全二叉树，一个堆存放在一个数组中，根结点为数组的第一元素；
//树的第二层从左至右存储在根结点之后，然后是第三层，依次类推；
//二叉堆有两种：大根堆和小根堆；
//大根堆的性质：某个结点最多和父节点一样大，即以任何一结点为根的子树其最大元素
//都在根结点；小根堆刚好相反；
typedef int ElemType;

long Parent(long i)
{//返回父节点标号
	if(i==0)
		return FALSE;
	else if(i==1||i==2)
		return 0;
	else return i/2;
}

long Left(long i)
{//返回左孩子点标号
	if(i==0)
		return 1;
	else return 2*i;
}

long Right(long i)
{//返回右孩子点标号
	if(i==0)
		return 2;
	else return 2*i+1;
}

void MaxHeapify(ElemType A[],long HeapSize,long i)
{//整堆，维持大根堆的性质，即各个子树的最大结点总在根结点
//一个二叉堆A，假设以Left(i)和Right(i)为根的两棵子树都已经是
//最大堆，A[i]可能小于其子女，所以要进行以下整堆；
	long l,r,largest;
	l=Left(i);
	r=Right(i);
	if(l<=HeapSize-1&&A[l]>A[i])
		largest=l;
	else
		largest=i;
	if(r<=HeapSize-1&&A[r]>A[largest])
		largest=r;
	if(largest!=i)
	{
		ElemType temp;
		temp=A[i];
		A[i]=A[largest];
		A[largest]=temp;
		MaxHeapify(A,HeapSize,largest);
	}
}

void BuildMaxHeap(ElemType A[],long HeapSize)
{//建堆，对二叉堆所有非叶子结点进行整堆，使A成为一个大根堆；
	long i=HeapSize/2-1;
	for(;i>=0;i--)
		MaxHeapify(A,HeapSize,i);
}

void HeapSort(ElemType A[],long HeapSize)
{//堆排序，利用大根堆的性质：最大元素总是在树根。
 //步骤：
 //依次取出树根元素，堆元素个数减一，把最后一个元素放到根结点，然后整堆；
	long i;
	BuildMaxHeap(A,HeapSize);
	for(i=HeapSize-1;i>0;i--)
	{
		ElemType temp;
		temp=A[0];
		A[0]=A[i];
		A[i]=temp;
		HeapSize=HeapSize-1;
		MaxHeapify(A,HeapSize,0);
	}
}