void HeapSort(int* a, int size)
{
	// 建小(da)堆
	HP hp;
	HeapInit(&hp);
	// O(N*logN)
	for (int i = 0; i < size; ++i)
	{
		HeapPush(&hp, a[i]);// O(N)空間復(fù)雜度
	}
	HeapPrint(&hp);
	// O(N*logN)  排序
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

void AdjustUp(HPDataType* a, HPDataType child){
	assert(a);
	//int child = php->size - 1;
	int parent = (child - 1) / 2;
	while (a[parent] > a[child] && parent >= 0)//小堆!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	{
		Swap(&a[parent], &a[child]);
		child = parent;
		parent = (child - 1) / 2;
	}
}

while (a[parent] < a[child] && parent >= 0)//大堆！！！！！！！！！！！！！！！！！！！
	{
		Swap(&a[parent], &a[child]);
		child = parent;
		parent = (child - 1) / 2;
	}

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

void AdjustDown(HPDataType* a, size_t size, size_t root){
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		//選出左右孩子小的那一個(gè)
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//向下調(diào)整，如果孩子小于父親，則交換，繼續(xù)向下調(diào)整
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

while (child < size)
	{
		//選出左右孩子大的那一個(gè)
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		//向下調(diào)整，如果孩子da于父親，則交換，繼續(xù)向下調(diào)整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

void HeapSort(int * a, int n){
	assert(a);
	//向上調(diào)整--建堆   向上建堆的復(fù)雜度比向下的高
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	//向下調(diào)整，必須保證子樹(shù)都是堆，所以從后往前
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);//這里的函數(shù)是對(duì)應(yīng)上文的建小堆的AdjustDown函數(shù)
	}//小堆--對(duì)應(yīng)降序排列
	
	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);//這里的函數(shù)是對(duì)應(yīng)上文的建小堆的AdjustDown函數(shù)
		--end;
	}
}
int main()
{
	//TestHeap();
	int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
	HeapSort(a, sizeof(a) / sizeof(int));

	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}