在前边我们讲完了二叉树的一些代码结构

现在呢我们需要进一步去细化

我们传参数组后，让数组里面的数据进行调整

如何调整成堆呢？

建堆

所以我们分装一个成堆的函数

还是先去断言

然后创建空间

这里我们需要用到一个memcpy函数

memcpy函数是用来进行拷贝的

memcpy用来做内存拷贝，你可以拿它拷贝任何数据类型的对象，可以指定拷贝的数据长度；

拷贝完后我们可以选择向下建堆或者向上建堆

向上建堆需要用到我们的向上调整函数，向下则用到向下调整函数

但要注意的是

通常我们都是使用向下建堆而不是向上

因为向上建堆它的复杂度是O(N*logN)而向下是O（N）

解释一下：

向上建堆，是从一开始的数据进行识别，也就是说，从底层开始一步步去建堆

相当于一个多*多

而向下建堆则是从上边开始建立，到最后的时候底层不需要堆建了，已经是堆建好的了

少了很多计算

所以相当于少*多

那么向上调整我们利用for循环去进行实现

让i为一，限制在size之内，每次加一然后利用我们的向上调整函数就可以实现

向下调整则不一样

这里不能让i为一了

因为我们是向下调整

所以需要从下还是往上进行

那么需要从他的size-1再-1/2开始也就是从最后一个父亲节点开始去建堆

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;

	// 向上调整，建堆 O(N*logN)
	//for (int i = 1; i < php->size; i++)
	//{
	//	AdjustUp(php->a, i);
	//}

	// 向下调整，建堆 O(N)
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

测试

在测试中我们需要注意到去建立大堆而不是小堆

让数组进行建堆首先是利用我们的向下调整函数，进行向下建堆

那么如何让数据从小到大排列好呢？

我们可以这样

利用分装好的Swap函数

然后交换头尾

再定义一个数等于n-1

让这个数在循环过程中不断--

并利用下调函数去调整

// 升序，建大堆还是小堆呢？大堆
// O(N*logN)
void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

int main()
{
	int a[] = { 3,6,1,5,8,9,2,7,4,0 };

	HeapSort(a, sizeof(a) / sizeof(int));
	return 0;
}

 这样就调试好了