【数据结构】二叉树之堆的实现-阿里云开发者社区

【数据结构】二叉树之堆的实现

2024-03-15 35

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】二叉树之堆的实现

🗒️前言：

在上一期的文章中我们学习了一些二叉树的知识，也了解了堆的概念。堆是一颗完全二叉树，分为大堆和小堆，今天我们将实现堆的各种功能。

一、二叉树的顺序结构

📒1.1顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

📒1.2堆的性质

堆中某个节点的之总是不大于或不小于其父亲节点的值

堆是一颗完全二叉树

📒1.3堆的分类

小堆：树中任意一个父亲都小于等于孩子

大堆：树中任意一个父亲都大于等于孩子

二、堆的实现

📒2.1堆的创建

堆的逻辑结构是树形结构，是我们想象出来的，实际上我们操作的数组，所以堆的创建和顺序表的结构相同。

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

📒2.2堆的初始化

我们有两种初始化的方式，一种是在初始化阶段不开辟空间，在插入过程中进行扩容；另一种是在初始化阶段就开辟空间。

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

void HeapInit(HP* php)
{
    assert(php); 
    php->size = 0;
    php->capacity = 5;
    php->a = (HPDateType*)malloc(sizeof(HPDateType) * capacity);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
}

📒2.3堆的插入

堆是使用顺序结构的数组来存储的，我们使用尾插插入数据更方便，然后将数据调整到合适的位置。

void HeapPush(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, sizeof(HPDataType) * newCapacity);
        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);
}

如图：在小堆中插入50，50比它的父亲小，所以要交换两数的位置。我们知道孩子的下标通过 parent=(child-1)/2 就可以得到父亲的下标，然后交换两数。

📒2.4向上调整数据

如果是小堆存储我们通过孩子的下标找到父亲，比较两数如果孩子小于父亲就交换，然后在向上比较，如果孩子不小于父亲就跳出循环。

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[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (parent - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

📒2.5堆的删除

我们使用挪动覆盖的方法删除根，会使关系混乱，剩下的值不一定是堆，而且效率很低。这里提供一种更好的方法，将根和最后一个值交换，然后删除，最后调整数据。

void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    Swap(&php->a[0], &php->a[php->size - 1]);
    --php->size;
    AdjustDown(php->a, php->size, 0);
}

这里要注意有数据的时候才能删除，所以要加入 assert(php->size > 0) 进行判断。

📒2.6向下调整数据

如果是小堆存储我们要找到左右孩子中较小的数，然后与父亲交换，再找到下一层重复步骤，直到找到叶节点结束。

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

📒2.7堆的销毁

我们使用动态开辟内存，要及时释放空间并置为空指针，不然会造成数据泄露。

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

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。