#include "Heap.h"
#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <string.h>
void Swap(HDataType* left, HDataType* right)
{
	HDataType temp = *left;
	*left = *right;
	*right = temp;
}
void AdjustDown(Heap* hp, int parent)
{
	// child作用：标记parent中较小的孩子
	// 默认情况下先标记左孩子，因为在完全二叉树，可能会存在节点有左没有右的情况
	// 但不会存在有右没有左的情况
	int child = parent * 2 + 1;
	int size = hp->size;
	while (child < size)   //表明parent的左孩子一定是存在的
	{
		// 找parent小的孩子
		if (child + 1 < size && hp->Compare(hp->array[child + 1], hp->array[child]))
		{
			child += 1;
		}

		// 检测parent是否满足对的特性
		if (hp->Compare(hp->array[child], hp->array[parent]))
		{
			Swap(&hp->array[parent], &hp->array[child]);
			// 较大的双亲和较小的孩子交换之后，大的元素往下移动
			// 可能会导致子树不满足堆的特性
			// 因此需要继续往下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			return;
		}
	}
}

void AdjustUp(Heap* hp)
{
	int child = hp->size - 1;
	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (hp->Compare(hp->array[child], hp->array[parent]))
		{
			Swap(&hp->array[child], &hp->array[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			return;
		}
	}
}

static void CheckCapacity(Heap* hp)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity * 2;
		// 1. 申请新空间
		int* temp = (HDataType*)malloc(sizeof(HDataType) * newCapacity);
		if (NULL == temp)
		{
			assert(0);
			return;
		}

		// 2. 拷贝元素
		for (int i = 0; i < hp->size; ++i)
		{
			temp[i] = hp->array[i];
		}

		// 3. 释放旧空间
		free(hp->array);
		hp->array = temp;
		hp->capacity = newCapacity;
	}
}

// 堆的构建
void HeapCreate(Heap* hp, HDataType a[], int n, COM com)
{
	// 1. 初始化hp
	hp->array = (HDataType*)malloc(sizeof(HDataType) * n);
	if (NULL == hp->array)
	{
		assert(0);
		return;
	}

	hp->capacity = n;
	hp->size = 0;

	// 2. 将数组中的元素拷贝到堆结构中
	memcpy(hp->array, a, n * sizeof(HDataType));
	hp->size = n;
	hp->Compare = com;

	for (int root = (n - 2) / 2; root >= 0; root--)
	{
		AdjustDown(hp, root);
	}
}


// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	if (hp->array)
	{
		free(hp->array);
		hp->array = NULL;
		hp->capacity = 0;
		hp->size = 0;
	}
}

// 堆的插入
void HeapPush(Heap* hp, HDataType x)
{
	// 检测容量是否足够
	CheckCapacity(hp);

	// 先将元素放入到堆中
	hp->array[hp->size] = x;
	hp->size++;

	// 将新插入的元素往上调整
	AdjustUp(hp);
}


// 堆的删除
void HeapPop(Heap* hp)
{
	if (HeapEmpty(hp))
	{
		return;
	}

	Swap(&hp->array[0], &hp->array[hp->size - 1]);
	hp->size -= 1;
	AdjustDown(hp, 0);
}


// 取堆顶的数据
HDataType HeapTop(Heap* hp)
{
	assert(!HeapEmpty(hp));
	return hp->array[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}


// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return 0 == hp->size;
}