堆的实现及其应用

堆的概念

        堆是完全二叉树，分为大堆和小堆。大堆：任何一个父亲都大于等于孩子，小堆：任何一个父亲都小于等于孩子。

堆的实现

目录

typedef int HPDataType;

typedef struct Heap
{ 
	HPDataType* a;
	int size;
	int capacity;
}HP;

//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//堆的初始化和销毁
void HPInit(HP* php);
void HPDestroy(HP* php);
//堆的插入和删除
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
//取堆数据和判空
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);
//向上调整和向下调整
void AdJustUp(HPDataType* a, int child);
void AdJustDown(HPDataType* a, int n, int parent);

1.堆的初始化

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

可以选择在堆的初始化过程直接对空间大小进行赋值，在这里选择不开空间。

2.堆的销毁

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

3.交换函数

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

4.向上调整

        堆在数组中存储，所以根节点的小标为孩子节点下标减一再除以二，向上调整即将孩子节点向上调整，直到满足要求的大堆(小堆)建成。

void AdJustUp(HPDataType* a, int child)
{
	int 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;
		}
	}
}

5.向下调整

void AdJustDown(HPDataType* a, int     n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//找出小的那个孩子
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

6.堆的插入

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;

	AdJustUp(php->a, php->size - 1);
}

我们选择在堆插入函数中进行空间的开创。

7.堆数据删除

        对于堆中数据的删除，删除叶子结点数据意义不大，我们主要是要删除顶层节点数据，思路将顶部数据进行调整到最后的叶子结点处，在对其进行删除即可。

void HPPop(HP* php)//向下调整算法,可用于topk问题（找最大(最小)的几个值）
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);

	php->size--;
	AdJustDown(php->a, php->size, 0);
}

8.取堆顶数据

        对于只有一条语句的函数，我们为了方便调控，仍进行函数调用。

HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

9.堆的判空

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

堆排序

建堆

        通过循环调用向上调整函数，可以将数组调整为堆。代码如下：

void HeapSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		AdJustUp(a, i);
	}
}

        另外，若使用向下调整建堆时间复杂度会更低

排序

升序建大堆

如果升序建小堆，将顶层最小数据取出后，导致后面数据顺序全部混乱，所以我们建大堆。

将最大的数往堆最后位置数据交换，再将其放入新数组的最后一位即可。代码如下：

void HeapSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		AdJustUp(a, i);
	}
	
	int end = n - 1;
	while (end > 0)
	{	
		Swap(&a[0], &a[end]);
		AdJustDown(a, end, 0);
		--end;
	}
}	

void AdJustDown(HPDataType* a, int     n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//找出小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
    //向上调整同理
	
}

降序建小堆

如果降序建大堆，将顶层最大数据取出后，导致后面数据顺序全部混乱，所以我们建小堆。

将最小的数往堆最后位置数据交换，再将其放入新数组的最后一位即可。代码如下：

void HeapSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		AdJustUp(a, i);
	}
	
	int end = n - 1;
	while (end > 0)
	{	
		Swap(&a[0], &a[end]);
		AdJustDown(a, end, 0);
		--end;
	}
}	

void AdJustDown(HPDataType* a, int     n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//找出小的那个孩子
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	//向上调整同理
}

如果觉得我写得不错的话，请别忘了点赞收藏加评论！！