typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
 struct BinTreeNode* _pLeft; //指向當(dāng)前節(jié)點左孩子
 struct BinTreeNode* _pRight; //指向當(dāng)前節(jié)點右孩子
 BTDataType _data; //當(dāng)前節(jié)點值域
}
// 三叉鏈
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; //指向當(dāng)前節(jié)點的雙親
 struct BinTreeNode* _pLeft; //指向當(dāng)前節(jié)點左孩子
 struct BinTreeNode* _pRight; //指向當(dāng)前節(jié)點右孩子
 BTDataType _data; //當(dāng)前節(jié)點值域
}；

void PreOrder(BTNode* root)//前序遍歷
{
	if (root == NULL)
	{
		printf("# ");//為空打印#
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
void InOrder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("# ");//為空打印#
		return;
	}
	InOrder(root->left);
	printf("%d", root->data);
	InOrder(root->right);
}
void PostOrder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("# ");//為空打印#
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

void HeapInit(Heap* ph)//堆的初始化
{
	assert(ph);
	ph->arr = NULL;
	ph->capacity = ph->size = 0;
}
void HeapDestroy(Heap* ph)//堆的銷毀
{
	assert(ph);
	free(ph->arr);
	ph->arr = NULL;
	ph->size = ph->capacity = 0;
}
void Swap(HeapDataType* child, HeapDataType* parent)//交換堆數(shù)組內(nèi)容
{
	HeapDataType tmp = *child;
	*child = *parent;
	*parent = tmp;
}
void AdjustUp(int* arr, int child)//向上調(diào)整函數(shù)
{
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (arr[parent] > arr[child])
		{
			Swap(&arr[child], &arr[parent]);//交換堆數(shù)組內(nèi)容
			child = parent;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* ph, HeapDataType x)//插入數(shù)據(jù)
{
	assert(ph);
	if (ph->capacity == ph->size)
	{
		int newcapacity = ph->capacity = 0 ? 4 : ph->capacity * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(ph->arr, sizeof(HeapDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc");
			exit(-1);
		}
		ph->arr = tmp;
		ph->capacity = newcapacity;
	}
	ph->arr[ph->size] = x;
	ph->size++;
	AdjustUp(ph->arr, ph->size - 1);//向上調(diào)整函數(shù)
}
void AdjustDown(HeapDataType* arr, int size, int parent)//向下調(diào)整函數(shù)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* ph)//堆的刪除
{
	assert(ph);
	assert(!HeapEmpty(ph));
	Swap(&ph->arr[0], &ph->arr[ph->size - 1]);
	ph->size--;
	AdjustDown(ph->arr, ph->size, 0);//向下調(diào)整函數(shù)
}
HeapDataType HeapTop(Heap* ph)//返回堆頂元素
{
	assert(ph);
	assert(!HeapEmpty(ph));
	return ph->arr[0];
}
bool HeapEmpty(Heap* ph)//堆的判空
{
	assert(ph);
	return ph->size == 0;
}
int HeapSize(Heap* ph)//返回堆中元素個數(shù)
{
	assert(ph);
	return ph->size;
}
void HeapPrint(Heap* ph)//打印堆中數(shù)據(jù)
{
	assert(ph);
	assert(!HeapEmpty(ph));
	for (int i = 0; i < ph->size; i++)
	{
		printf("%d ", ph->arr[i]);
	}
	printf("\n");
}

void HeapSort(int* arr, int sz)
{
	int end1 = (sz - 1 - 1) / 2;//求最后一個節(jié)點的父節(jié)點，這個父節(jié)點即最后一個非葉子節(jié)點
	for (int i = end1; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}
	//開始排序
	//升序 -- 用大堆
	//降序 -- 用小堆
	int end2 = sz - 1;
	while (end2 > 0)
	{
		Swap(&arr[0], &arr[end2]);
		AdjustDown(arr, end2, 0);
		end2--;
	}
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}