数据结构【堆的概念及接口实现】

1.关于堆你应该知道的？

堆是一棵完全二叉树，堆中的元素存储在一个一维数组中，对于任意节点，如果该节点小于其左右孩子，我们把这种结构叫做小堆；如果大于其左右孩子，我们把这种结构叫做大堆。

堆的特性：

1. 堆顶元素一定是堆中所有元素最大（最小）的
2. 堆总是一棵完全二叉树
3. 堆中的某个节点的值一定是不大于或者不小于其父节点的值

2. C语言实现堆的接口

typedef int HPDataType;

typedef struct Heap {
	HPDataType* _array;
	int _capacity;
	int _size;
}Heap;


void Swap(HPDataType* x, HPDataType* y) {
	HPDataType temp = *x;
	*x = *y;
	*y = temp;
}

void CheckCapacity(Heap* hp) {
	assert(hp);
	if (hp->_size == hp->_capacity) {
		int newCapacity = hp->_capacity * 2;
		HPDataType* pTemp = (HPDataType*)malloc(sizeof(HPDataType)*newCapacity);
		if (NULL == pTemp) {
			assert(0);
			return;
		}
		for (int i = 0; i < hp->_size; i++) {
			pTemp[i] = hp->_array[i];
		}
		free(hp->_array);
		hp->_capacity = newCapacity;
		hp->_array = pTemp;
	}
}

//堆向下调整算法
void AdjustDown(HPDataType* array, int size, int parent) {
	//默认用child标记parent的左孩子，完全二叉树只有一个孩子的话，一定是左孩子
	int child = parent * 2 + 1;
	//找双亲孩子中较小的孩子
	while (child < size){
		if (child + 1 < size && array[child + 1] < array[child]) {
			child += 1;
		}
		if (array[child] < array[parent]) {
			Swap(&array[child], &array[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			return;
		}
	}
}

//堆向上调整算法
void ADjustUP(HPDataType* array, int size, int child) {
	int parent = (child - 1) / 2;
	while (child) {
		if (array[child] < array[parent]) {
			Swap(&array[child], &array[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			return;
		}
	}
}

//空堆的初始化
void InitEmptyHeap(Heap* hp,int capacity) {
	assert(hp);
	hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*capacity);
	if (NULL == hp->_array) {
		assert(0);
		return;
	}

	hp->_capacity = capacity;
	hp->_size = 0;
}

//堆的初始化
void InitHeap(Heap* hp, HPDataType* array, int size) {
	assert(hp);
	hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size);
	if (NULL == hp->_array) {
		assert(0);
		return;
	}

	hp->_capacity = size;
	for (int i = 0; i < size; i++) {
		hp->_array[i] = array[i];
	}
	hp->_size = size;
	//找到最后一个非叶子节点
	int root = (size - 2) / 2;
	for (; root >= 0; root--){
		AdjustDown(hp->_array, size, root);
	}
}

//在堆中插入元素
void InsertHeap(Heap* hp, HPDataType* data) {
	CheckCapacity(&hp);
	hp->_array[hp->_size] = data;
	hp->_size++;
	ADjustUP(hp->_array, hp->_size, hp->_size - 1);
}

//删除一个堆元素
void EarseHeap(Heap* hp) {
	if (HeapEmpty(hp))
		return;
	Swap(&hp->_array[0], &hp->_array[hp->_size - 1]);
	hp->_size -= 1;
	AdjustDown(hp->_array, hp->_size, 0);
}

//获取堆中有效元素个数
int HeapSize(Heap* hp) {
	assert(hp);
	return hp->_size;
}

//判断堆是否为空
int HeapEmpty(Heap* hp) {
	assert(hp);
	return 0 == hp->_size;
}

//获取堆顶元素
HPDataType HeapTop(Heap* hp) {
	assert(hp);
	return hp->_array[0];
}

//销毁堆
void DestroyHeap(Heap* hp) {
	assert(hp);
	if (hp->_array) {
		free(hp->_array);
		hp->_capacity = 0;
		hp->_size = 0;
	}
}