数据结构---------堆排序

    说到堆排序，它的思想来源于优先队列，我们首先来说一下什么是优先队列。

一、优先队列

1.优先队列的定义：优先队列是允许以下两种操作的数据结构：Insert（插入）相当于入队、DeleteMin（删除最小元）。

2.使用数据结构：相比于单链表和二叉排序树的缺点，我们使用二叉堆这种结构，它有两个重要的性质就是：

4.思想：

声明：

#include <stdio.h>#include <stdlib.h>#define ElementType int/*优先队列数组实现*/typedef struct HeapStrcut	//堆结构{	int Capcity;	int Size;	ElementType *Elements;}*PRiorityQueue;PriorityQueue Initialize(int MaxElements);  //创建初始化优先队列void Insert(ElementType X, PriorityQueue H);//插入ElementType DeleteMin(PriorityQueue H);	    //删除最小节点int IsEmpty(PriorityQueue H);		    //判断优先队列是否为空int IsFull(PriorityQueue H);		    //判断优先队列是否已满实现：
/*创建初始化优先队列小顶堆，最小元在根节点*/PriorityQueue Initialize(int MaxElements){	PriorityQueue H;	//申请优先队列结构空间	H = (PriorityQueue)malloc(sizeof(struct HeapStrcut));	if(NULL == H)	{ 		printf("Out of space./n");		exit(-1);	}	//申请存储数据数组Elements空间	H->Elements = (ElementType *)malloc(sizeof(ElementType)*MaxElements);	if (H->Elements == NULL)	{		printf("Out of space./n");		exit(-1);	}	//初始化优先队列	H->Capcity = MaxElements;	H->Size = 0;}/*插入，交换而实施的赋值语句为d+1*/void Insert(ElementType X, PriorityQueue H){	int i;	if(IsFull(H))	{ 		printf("The PriorityQueue is full./n");		exit(-1);	}		for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)		H->Elements[i] = H->Elements[i / 2];	H->Elements[i] = X;}//我的插入写法，交换而实施的赋值语句为3dvoid Insert2(ElementType X, PriorityQueue H){	int i, tmp;	if (IsFull(H))	{		printf("The PriorityQueue is full./n");		exit(-1);	}	H->Elements[++H->Size] = X;	tmp = H->Elements[H->Size];	for (i = H->Size; i / 2 > 0; i /= 2)		if (H->Elements[i / 2] > H->Elements[i])			H->Elements[i] = H->Elements[i / 2];		else			break;	H->Elements[i] = tmp;}/*删除最小节点*/ElementType DeleteMin(PriorityQueue H){	int i, child;	ElementType MinElement, LastElement;	if (IsEmpty(H))	{		printf("The PriorityQueue is empty./n");		exit(-1);	}	MinElement = H->Elements[1];	LastElement = H->Elements[H->Size--];	for (i = 1; i * 2 <= H->Size; i = child)	{		//查找较小的子节点		child = i * 2;		if (child != H->Size && H->Elements[child + 1] < H->Elements[child])			child++;		//下滤操作		if (LastElement > H->Elements[child])			H->Elements[i] = H->Elements[child];		else			break;	}	H->Elements[i] = LastElement;	return MinElement;}/*判断优先队列是否为空*/int IsEmpty(PriorityQueue H){	return H->Size == 0;}/*判断优先队列是否已满*/int IsFull(PriorityQueue H){	return H->Size == H->Capcity;}/*显示优先队列元素*/void show(PriorityQueue H){	int i;	for (i = 1; i <= H->Size; i++)		printf("%d/t", H->Elements[i]);	printf("/n");}int main(){	int max_elements, flag=1, choose, value;	//构建优先队列	printf("开始构建优先队列/n");	printf("请输入优先队列大小：/n");	scanf("%d", &max_elements);	PriorityQueue H = Initialize(max_elements);		//优先队列操作	while (flag)	{		printf("请输入操作，1.插入 2.删除最小元 3.显示优先队列元素./n");		scanf("%d", &choose);		switch (choose)		{		case 1:			printf("请输入插入元素/n");			scanf("%d", &value);			Insert(value, H);			break;		case 2:			DeleteMin(H);			show(H);			break;		case 3:			show(H);			break;		default:			flag = 0;			break;		}	}    return 0;}
二、堆排序
1.思路：将要排序的数据构建成小顶堆，交换根与最后节点，下滤重新构建堆。
2.实现：
       数组实现，下标从0开始：
/*堆排序思路：堆排序分为构建堆、删除最值、调整堆即上滤下滤操作。方法：使用数组代替ADT（抽象数据类型）的方式实现初始堆数组下标从零开始。总结：时间复杂度为N*logN。*///上滤操作void PercDown(ElementType A[], int i, int N)	//i为父节点下标{	int replChild;		//下滤操作时用来与根节点交换的孩子节点下标	ElementType tmp;	//一般利用交换进行的排序都要有一个tmp变量	//每次开始都要取出最顶点下标，所以可以写在for语句头中作为初始条件	//遍历的条件就是父节点还有孩子	//执行完此次下滤操作后需要找到下次下滤操作的父节点，所以我们也可以写到for语句头	for (tmp = A[i]; 2*i+1 < N; i = replChild)	//i = replChild是在语句体执行之后执行的	{		if (2 * i + 1 != N - 1 && A[2 * i + 1] < A[2 * i + 1 + 1])//若右孩子存在且右孩子大则将右孩子下滤			replChild = 2 * i + 1 + 1;		if (2 * i + 1 != N - 1 && A[2 * i + 1] > A[2 * i + 1 + 1])//若右孩子存在且右孩子小则将左孩子下滤			replChild = 2 * i + 1;		if(2 * i + 1 == N - 1)		//若右孩子不存在则将左孩子下滤				replChild = 2 * i + 1;		//书上方法		//replChild = 2*i+1;		//if (replChild != N - 1 && A[replChild + 1] > A[replChild])		//	replChild++;		//满足孩子比父亲数据大,将孩子数据赋值父亲数据,		//否则，不满足堆结构，不需要下滤跳出循环		if (tmp < A[replChild])			A[i] = A[replChild];		else			break;	}	A[i] = tmp;}//堆排序void HeapSort(ElementType A[], int N){	int i, temp;;	for (i = N / 2; i >= 0; i--)		PercDown(A, i, N);	for (i = N - 1; i > 0; i--)	{	//交换根与最后的节点数据		temp = A[0];		A[0] = A[i];		A[i] = temp;		PercDown(A, 0, i);	}}
3.分析：堆排序的时间复杂度为O（longN），构建N个数据的二叉堆需要O（N）时间，DeleteMin需要O（NlogN）时间。
              堆排序是一个稳定的排序，无论起始的数据序列是如何的。