堆的实现 堆排序-ag真人游戏

一，堆的定义

1.概念

堆就是一棵可以自我平衡的完全二叉树，存储结构连续，可看作是顺序表。

2.性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

3.结构

堆的逻辑结构为一颗完全二叉树，但实际上在内存中的存储是连续的，那么要实现它就可以想到用顺序表来实现。

定义

数据类型记得重定义

依据上述内容，我们用顺序表来实现堆

size记录有效元素个数，capacity记录空间大小

typedef int hpdatatype;
typedef struct heap
{
	hpdatatype* a;
	size_t size;
	size_t capacity;
}hp;

初始化和销毁

指向顺序表开头的的地址a置空

空间大小和有效元素个数都为0

void heapinit(hp* php)
{
	assert(php);
	php->a = null;
	php->capacity = php->size = 0;
}

因为空间是连续开辟的，只需要释放起始地址，后面的空间会随之释放

之后将空间和元素个数置0即可 

void heapdestroy(hp* php)
{
	assert(php);
	free(php->a);
	php->a = null;
	php->size = php->capacity = 0;
}

数据入队

数据入堆=插入顺序表

先判断空间大小是否足够，初始空间给4个，之后每次扩容原容量的二倍

用realloc进行扩容，记得进行判断，这里我暴力些，直接断言

记得更新空间大小

注：堆有大堆和小堆，插入数据后，必须保证堆的结构还是大堆或小堆

无论是大堆或小堆，最大数据或最小数据都在堆顶，若插入数据不符合堆的结构，那么必须将数据向上调整。是孩子结点和双亲结点间的调整

堆的插入图解

交换函数 

从图看出必须进行两个数的交换，那么我们单独写出一个交换函数

void swap(hpdatatype* pa, hpdatatype* pb)
{
	hpdatatype* tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

下面是插入数据的代码，为了简便一点，我们把向上调整单独拿出来

向上调整函数 

注意：存储结构是顺序表，下标从0开始，若顺序表size=1，有效数据为1，那么数据在下标为0的位置上，所以child=php->size-1，这里面child和parent为元素下标。

//向上调整
void up(hpdatatype* a,size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void heappush(hp* php, hpdatatype x)
{
	assert(php);
	//插入元素
	if (php->size==php->capacity)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		hpdatatype* tmp = (hpdatatype*)realloc(php->a,sizeof(hpdatatype)*newcapacity);
		assert(tmp);
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size  ;
	//保证是堆的结构
	//向上调整
	size_t child = php->size - 1;
	//size_t parent = (child-1) / 2;
	//while (child>0)
	//{
	//	if (php->a[child] < php->a[parent])
	//	{
	//		//hpdatatype data = php->a[parent];
	//		//php->a[parent] = php->a[child];
	//		//php->a[child] = data;
	//		swap(&php->a[child], &php->a[parent]);
	//		child = parent;
	//		parent = (child - 1) / 2;
	//	}
	//	else
	//	{
	//		break;
	//	}
	//}
	up(php->a,child);
}

出堆

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

图解

交换后保持堆的结构，必须将数据即堆顶元素与他的最小或最大孩子进行交换（要看是大堆还是小堆，小堆和小孩子交换，大堆和大孩子交换） 

向下调整函数

向下调整必然要循环执行，必须要左孩子和右孩子都小于有效个数size，左孩子一定小于右孩子，判断条件只需要右孩子小于size即可。

代码以小堆为例：

      我分了两条逻辑线（有些繁琐，下面有优化）：

      左孩子小的情况和右孩子小的情况

      交换数据，双亲结点和两个孩子结点下标进行更新

      当数据相等时退出循环

void down(hpdatatype* a,size_t parent,size_t size)
{
	size_t lchild = parent*2   1;
	size_t rchild = parent*2   2;
	while (rchild a[lchild])
			{
				swap(&a[parent], &a[lchild]);
				parent = lchild;
				lchild = parent*2   1;
				rchild = parent*2   2;
			}
		}
		else if (a[lchild]>a[rchild])
		{
			if (a[parent] > a[rchild])
			{
				swap(&a[parent], &a[rchild]);
				parent = rchild;
				lchild = parent*2   1;
				rchild = parent*2  2;
			}
		}
		else
		{
			break;
		}
	}
}

向下调整函数优化

对上面代码的优化，直接确定一个孩子child，默认它是左孩子，第一个if处必须判断child 1小于size，防止越界。

如果右孩子小于左孩子，左孩子 直接等于右孩子，否则不变

之后直接判断双亲结点和孩子的大小完成互换或者退出

//down优化
void down(hpdatatype* a, size_t parent, size_t size)
{
	size_t child = parent * 2   1;
	while (child < size)
	{
		if (child   1 

//删除堆顶数据
//互换堆顶和末尾数据，向下调整
void heappop(hp* php)
{
	assert(php);
	assert(php->size > 0);
	size_t parent = 0;
	swap(&php->a[0],&php->a[php->size-1]);
	php->size--;
	down(php->a,parent,php->size);
}

bool heapempty(hp* php)
{
	assert(php);
	return php->size == 0;
}
size_t heapsize(hp* php)
{
	assert(php);
	return php->size;
}
hpdatatype heaptop(hp* php)
{
	assert(php);
	assert(php->size>0);
	return php->a[0];
}

void heapprint(hp* php)
{
	assert(php);
	for (size_t i=0;isize;i  )
	{
		printf("%d ",php->a[i]);
	}
	printf("\n");
}

//堆排序
void heapsort(int* a,int size)
{
	hp hp;
	heapinit(&hp);
	for (int i = 0;i