梳理和实现数据结构中的堆

首先看看为什么引入堆和堆的定义

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。

而完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储

如果有集合，把它的所有元素按完全二叉树的顺序存储方式存储，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

          1.堆中某个节点的值总是不大于或不小于其父节点的值；

          2. 堆总是一棵完全二叉树。

OK，接下查看接口

#include 
#include 
#include 
#include 

typedef int HeapDataType;
typedef struct Heap Heap;

//创建动态顺序结构的堆
struct Heap
{
	HeapDataType* a;
	size_t size;
	size_t capacity;
};
//交换函数
//向上调整堆
//向下调整堆
void Swap(HeapDataType *pa, HeapDataType *pb);
void AdjustUp(HeapDataType* a, size_t child);
void AdjustDown(HeapDataType* a, size_t size, size_t root);

//堆的初始化和销毁及打印有效值
void HeapInit(Heap* php);
void HeapDestroy(Heap* php);
void HeapPrint(Heap* php);

//有效值的插入与删除
void HeapPush(Heap* php,HeapDataType x); 
void HeapPop(Heap* php);

//堆的断空，求有效值个数，返回堆顶的值
bool HeapEmpty(Heap* php);
size_t HeapSize(Heap* php);
HeapDataType HeapTop(Heap* php);

第一部分：堆的初始化和销毁及有效值的打印

//初始化堆
void HeapInit(Heap* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

//销毁堆
void HeapDestroy(Heap* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

//打印堆的值
void HeapPrint(Heap* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

第二部分：堆的有效值插入与删除

//在最后插入数据，然后调整
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HeapDataType* tmp = realloc(php->a, sizeof(HeapDataType)*newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);

}

//删除堆顶的数据，然后调整
//将根位置的值与最后一个位置的值交换，在向下调整
//向下调整：跟左右孩子中，小的孩子交换(小堆)
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[(php->size)-1]);

	php->size--;
	AdjustDown(php->a, php->size,0);

}

=================================================================
关于数据的插入与删除，涉及另外三个接口
分别是：数据交换函数；向上调整堆函数；向下调整堆函数

//交换函数
void Swap(HeapDataType *pa, HeapDataType *pb)
{
	*pa = *pa ^ *pb;
	*pb = *pa ^ *pb;
	*pa = *pa ^ *pb;
}

//向上调整堆
void AdjustUp(HeapDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;

	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//向下调整堆
void AdjustDown(HeapDataType* a,size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;

	while (child < size)
	{
		if ((child+1) < size && a[child] > a[child+1])
		{
			child++;
		}//找到较小的孩子

		if (a[child] < a[parent])
		{
			Swap(&a[child],&a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break; 
		}
	}

}

第三部分：堆的断空，求有效值个数，返回堆顶的值

​
//断空
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

//求有效值个数
size_t HeapSize(Heap* php)
{
	assert(php);
	return php->size;
}
//返回堆顶的值
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size>0);
	return php->a[0];
}

​

好啦，本篇博客分享到此为止，如果内容有错误还请在评论区指正。

希望看完本篇博客有所收获的小伙伴能够点赞和转发。

后续也会带来更多干货！