实现二叉树_堆

数据人与超自然意识 · 2025-1-22 07:59:11

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

x

一. 堆的实现

在上一节中我们知道了堆的数据布局，实在就是一种特殊的完全二叉树，堆的底层数据布局就是数组，以是我们就可以界说堆的布局：

//定义堆的结构--数组
typedef int HPDataType;
typedef struct Heap
{
HPDataType* arr;
int size;//有效的数据个数
int capacity;//空间大小
}HP;
void HPinit(HP* php);//堆的初始化
void HPdistroy(HP* php);//堆的销毁
void HPPush(HP* php, HPDataType x);//向堆中插入数据
void AdjustUP(HPDataType* arr, int child);//堆的向上调整法
void Swap(HPDataType* x, HPDataType* y);//数据交换
void HPpop(HP* php);//删除数据
void AdjustDown(HPDataType* arr, int parent, int n);//堆的向下调整算法
HPDataType HPTop(HP* php);//取堆顶数据

复制代码

下面是详细的算法实现：

void HPinit(HP* php)//堆的初始化
{
assert(php);
php->arr = NULL;
php->size = php->capacity = 0;
}
void HPdistroy(HP* php)//堆的销毁
{
if (php->arr)
free(php->arr);
php->arr = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* x, HPDataType* y)//数据交换
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUP(HPDataType* arr, int child)//堆的向上调整法
{
int parent = (child - 1) / 2;
while (child >= 0)
{
if (arr[child] < arr[parent])
{
Swap(&arr[parent], &arr[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 : 2 * php->capacity;
HPDataType* tmp = realloc(php->arr, newCapacity * sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail!");
exit(1);
}
php->arr = tmp;
php->capacity = newCapacity;
}
}
php->arr[php->size] = x;
//进行堆的调整（完成我们的大堆或者小堆）
AdjustUP(php->arr, php->size);
++php->size;
}
//堆的向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
int child = parent * 2 + 1;//左孩子
while (child<n)
{
//找到左右孩子中的最小值
if (child + 1 < n && arr[child] > arr[child + 1])
{
child++;
}
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//在堆中删除数据是删除堆顶的数据，所以在我们删除完一个数据之后还要保持这个堆的结构是原本的小堆或者大堆，还要进行数据调整
void HPpop(HP* php)//删除数据
{
assert(php && php->size);
//arr[0] arr[size-1]
Swap(&php->arr[0], &php->arr[php->size - 1]);
//向下调整算法
AdjustDown(php->arr, 0, php->size);
--php->size;
}
//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
HPDataType HPTop(HP* php)//取堆顶数据
{
assert(php && php->size);
return php->arr[0];
}

复制代码

上面就是对于堆这样一个数据布局中数据的插入、删除、以及如何完成我们想要的大堆照旧小堆等，通过算法一一实现。
二. 向上调整算法

我们在上面的算法中可能会看到一个向上调整算法，这是一个比较紧张的算法，用于完成我们想要的数据布局。如何来理解呢?首先我们就拿小堆来举例子，如果我们现在要完成一个小堆的数据布局，我们首先要往一个数组中插入数据：

以是第一步，我们来插入数据，先判断空间是否足够，如果不敷的话就扩容，末了再往数组中插入数据，这是比较最根本的步调，然后再来实现我们要的小堆，这里就必要我们的AdjustUP向上调整算法：

根据上面的图片我们来做对代码的解释，如图所示，我们就拿17 20 10 13 19 15 这几个数字来完成我们的小堆，我们在AdjustUP函数中传入（php->arr, php->size），实在就是指数组，以及传入的末了一个数据，以是当我们传入了两个数据之后，我们就要开始比较了，20是孩子结点，通过计算找到父亲结点，然后比较二者的巨细，因为我们这次要完成的是小堆，以是此时两者不消交换，但是当在传入数据10的时候，通过计算发现10<17，要交换。但是如果还继续传入数据的话，我们就要一步步继续向上比较，以是此时我们要让child即是来的parent，parent继续即是（child-1）/2，继续向上比较，直到child小于0，以是我们的while循环条件是（child>=0)，我们来调试一下判断我们的代码是否正确：

由此看出来我们确实实现了小堆的操作，大家可以自己操作实现一下。
三. 向下调整算法

堆的删除的删除堆顶的数据，但是如果直接删除堆顶的数据之后，我们本来的大堆大概小堆的顺序就会改变，可能发生顺序的紊乱，以是如果我们要删除堆中的一个数据的话，也就是出堆，出的是堆顶的数据，我们一般采用的是交换堆顶数据和最末尾的数据：