数据结构---堆

用户11305458

发布于 2024-10-09 16:14:04

2130

文章被收录于专栏：学习学习

堆的概念及结构

堆的要求 堆必须满足完全二叉树 堆的分类 堆分为两种： 1.小堆：任何一个孩子大于父亲 2.大堆：任意一个孩子都小于父亲 堆的结构 堆的逻辑结构：二叉树堆的物理结构：数组堆的用处：堆排序、topk 堆的特点 大堆可以找到最大值，小堆可以找到最小值

堆的接口

堆的表示

堆的底层用的是顺序表，所以堆的表示和顺序表是一样的。

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

堆的初始化

因为堆的底层是数组，所以初始化和顺序表一样，可以先给一定的空间，也可以不给，代码如下：

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

在堆中插入数据

在堆中插入数据我们要注意，有以下几种情况：如果所示：

我们要在这个大堆的最后插入一个数据，我们可以看出这个堆事一个大堆，当我们插入一个比3小的数据时，我们是不用调的，因为它满足大堆的要求（所有的孩子都比父亲小），当我们插入比3大的数据时，我们就应该把这个数据往上调，通过比较孩子和父亲的大小，然后交换两个数据从而达到了调整的方法，这种方法我们把它叫做向上调整算法。根据文字描述，可以得出下面的代码：

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

上面用到的Swap函数如下：

void Swap(HPDataType* ps, HPDataType* pq)
{
    HPDataType tmp = *ps;
    *ps = *pq;
    *pq = tmp;
}

在插入数据时，必须先验证一下空间是否足够，如果空间不够，就要开辟新的空间

//假设实现的是小堆
void HPPush(HP* php, HPDataType x)
{
    assert(php);
    //扩容
    if (php->capacity == php->size)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* newnode = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (newnode == NULL)
        {
            perror("realloc fail\n");
            return;
        }
        php->a = newnode;
        php->capacity = newcapacity;
    }
    //插入数据
    php->a[php->size] = x;
    php->size++;
    AdJustUp(php->a, php->size - 1);
}

取出堆顶的数据

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

删除栈顶的数据

注意：如果直接删除栈顶的数据，整个堆就会变得很乱，所以，删除堆顶的数据用到的方法是：先将栈顶的数据和最后一个孩子交换，然后将最后一个数据删除，删除之后再用向下调整算法将栈顶的数据调到孩子的位置，以满足堆的要求。 向下调整算法

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

删除堆顶的数据

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

判断栈是否为空

判断栈是否为空可以直接通过size来判断

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

堆的销毁

堆的销毁和顺序表的销毁一样

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-04-02，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度