二叉堆的实现

文章目录

堆
- 堆的概念及性质
二叉堆的实现
- Heap.h
- Heap.c
- - 堆的初始化
  - 堆的销毁
  - 向堆中插入数据
  - 删除堆中的数据
  - 找堆顶元素
  - 判断堆是否为空
  - Heap.c完整代码
- test.c

堆

堆的概念及性质

在这里插入图片描述

二叉堆的实现

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

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

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);

Heap.c

堆的初始化

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

堆的本质是数组，初始化让数组首地址指向空，数组大小（元素个数）和容量赋值为0.

堆的销毁

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

首先断言确保传入的堆存在，再释数组地址并置空，将数组大小和容量重置为0

向堆中插入数据

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");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	Adjustup(php->a, php->size - 1);
}

前面先判断数组的空间是否足够，不够要先进行扩容，用newcapacity代表新数组的容量，如果初始容量为0则给newcapacity赋值为4，如果一开始有容量就将容量扩大为原来的2倍。（为什么扩容2倍呢？因为如果选更大的倍数扩容容易浪费过多的内存空间，而每次扩容太少又容易造成多次扩容的情况，增加算法是时间复杂度。）扩容完后将a指向新扩容的地址，新的容量赋值给capacity。如果扩容失败程序结束。

	php->a[php->size] = x;
	php->size++;
	Adjustup(php->a, php->size - 1);

之后将要插入的值赋给a的末位，然后根据堆的性质要对新插入的数进行位置调整，这里将向上调整用另一个函数实现。

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

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

这里实现的是大堆（根节点最大）的向上调整，swap函数对要调整的两值进行交换，首先我们要知道在二叉堆中子节点和父节点的关系。
在这里插入图片描述
有图可以看出56和30是70的第一，第二孩子，我们很容易得到他们的下标关系，孩子1的下标是父节点下标的2倍+1，孩子2的下标是父节点下标的2倍+2。由此我们能反推父节点的下标是（子节点下标-1）/2（整数的除法省略小数，故2个孩子这样计算的结果都是父节点的下标）。接下来就是判断大小，子节点的数大就和父节点交换，再和新的父节点比较，直到找到合适的位置或称为根节点就调整完成了。

删除堆中的数据

删除堆中的数据之前我们要先考虑删除数据后的效果，因为我们堆的性质是根节点最大或最小，所以删根节点能让我们找出堆中数据的大小循序。首先我们直接删根节点的数据试试，在上图的大堆中，我们如果直接把70删去，那么重新构成大堆就要下面的数据一一向上调整，很麻烦。所以我们不妨将根节点和尾节点交换位置，交换后将就的根节点删除，新的根节点执行一次向下调整就好了。

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	php->a[0] = php->a[php->size - 1];
	php->size--;
	Adjustdown(php->a, php->size, 0);

}

这里同样将向下调整放在另一函数里

void Adjustdown(HPDataType* a, int size,int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1<size&&a[child + 1] >a[child])
		{
			child++;
		}
		if (a[parent] <a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

大堆中向下调整是和子节点中大的值交换，一开始我们不知道哪个子节点是更大的，所以不妨假设第一个子节点最大，如果假设不成立就让子节点++，变成第二子节点

	if (child+1<size&&a[child + 1] >a[child])
		{
			child++;
		}

找堆顶元素


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

判断堆是否为空

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

这里判空的作用便于遍历堆的元素。

Heap.c完整代码

#include"Heap.h"

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


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

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

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

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");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	Adjustup(php->a, php->size - 1);
}

void Adjustdown(HPDataType* a, int size,int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child+1<size&&a[child + 1] >a[child])
		{
			child++;
		}
		if (a[parent] <a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	php->a[0] = php->a[php->size - 1];
	php->size--;
	Adjustdown(php->a, php->size, 0);

}


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

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

test.c

接下来看看我们实现的大堆的效果，第一行是打印堆的元素，第二是利用堆来排序

#include"Heap.h"

int main()
{
	HP hp;
	HPInit(&hp);
	int a[] = { 2,8,6,49,5,3,11,3,7 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	for (int i = 0; i < 9; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}
	return 0;