数据结构与算法（3）-- 堆排序

 待补全~

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

#define SIZE 10
#define HEAPSIZE 10

typedef struct heaps{
	int a[SIZE];
	int heapsize;
}heap;

heap *heapcreate()
{
	heap *p = (heap *)malloc(sizeof(heap));
	if(p == NULL)
	{
		exit(1);
	}

	p->heapsize = HEAPSIZE; 
	return p;
}

void heapmodify(heap *h, int index)   //将index节点以下节点的最大值，逐层往上挪，使满足堆的要求
{
	//(h->a)[index] = val;
	int tmp, current, right, left;

	int i;
	for(i=index; i<(h->heapsize+1)/2;)     //从index节点到最后一个有子节点的节点
	{
		current = (h->a)[i];
		right = (h->a)[2*i+2];
		left = (h->a)[2*i+1];
		
		if(2*i+2 < h->heapsize)   //最后一个有子节点的节点，有两个子节点
		{
			if(left < right && right > current)    //右节点最大，与父节点交换
			{
				tmp = current;
				(h->a)[i] = right;
				(h->a)[2*i+2] = tmp;
				i = 2*i + 2;		
			}
			else if(left > right && left > current)   //左节点最大，与父节点交换
			{
				tmp = current;
				(h->a)[i] = left;
				(h->a)[2*i+1] = tmp;
				i = 2*i +1;
			}
			else
			{
				break;               //已满足堆要求，无需进入下一层，结束循环
			}
		}
		else           //最后一个有子节点的节点，只有一个左子节点
		{
			if(left > current)     //左节点比父节点大，与之交换
			{
				tmp = current;
				(h->a)[i] = left;
				(h->a)[2*i+1] = tmp;
				i = 2*i +1;
			}
			else
			{
				break;     //已满足堆要求，无需进入下一层，结束循环
			}
		}
	}
}

void heapify(heap *h)     //构建堆
{
	int heapsize = (h->heapsize+1)/2;

	int i;
	for(i=heapsize-1; i>=0; i--)
	{
		heapmodify(h, i);
	}
}

void printall(heap *h)
{
	printf("heapsize : %d\n", h->heapsize);
	int i;
	for(i=0; i<h->heapsize; i++)
	{
		printf("%d-",(h->a)[i]);
	}

	printf("\n");
}

void main()
{
	heap *p = heapcreate();

	int i;
	for(i=0; i<p->heapsize; i++)
	{
		scanf("%d", &((p->a)[i]));	
	}

	printall(p);
	heapify(p);
	printall(p);
}