数据结构之堆的实现(图解➕源代码)

这篇具有很好参考价值的文章主要介绍了数据结构之堆的实现(图解➕源代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、堆的定义

        首先明确堆是一种特殊的完全二叉树,分为大根堆和小根堆,接下来我们就分别介绍一下这两种不同的堆。

1.1 大根堆(简称:大堆)

        在大堆里面:父节点的值 ≥ 孩子节点的值

        我们的兄弟节点没有限制,只要保证每个父节点都≥孩子节点就行。

数据结构之堆的实现(图解➕源代码),数据结构,算法

1.2 小根堆(简称:小堆)

        在小堆里面:父节点的值  孩子节点的值

        同样兄弟节点也没有限制,只要保证每个父节点都≤孩子节点就行。

数据结构之堆的实现(图解➕源代码),数据结构,算法

这里就又用到了我们的父节点和孩子节点的位置关系了,我们可以用顺序结构来模拟完全二叉树,也就是数组来实现,话不多说,直接给公式和图形:

parent = (child-1)/2;   (任意一个child节点)

child1 = parent*2 + 1;

child2 = parent*2 + 2;

这里是运用数组下标进行计算

数据结构之堆的实现(图解➕源代码),数据结构,算法

二、堆的实现

        我们形成堆有两种方法,一种是向下调整,一种是向上调整,在未来,经常会用到向下调整,所以我们只介绍这种方法。

2.1 向下调整法

        什么是向下调整呢?就是把我们的完全二叉树从从上往下建堆,使用向下调整法的前提就是根的左右子树必须是堆。

首先我们要建小堆,先找到同一层的小的那个和父节点交换,以此类推,直到10到叶节点或者没有比他小的。

数据结构之堆的实现(图解➕源代码),数据结构,算法

数据结构之堆的实现(图解➕源代码),数据结构,算法

2.2 堆的定义

在这里我们的堆的存储结构都是数组,所以在定义的时候跟定义顺序表一样,只不过在插入删除上有区别

typedef struct Heap
{
    int* arr; 
    int capacity; //数组的容量
    int size; //有效的元素个数
}Heap;

2.3 堆的初始化

//堆的初始化
void HeapInit(Heap* php)
{
    assert(php);
    php->arr = NULL;
    php->capacity = 0;
    php->size = 0;
}

2.4 堆的创建

//堆的创建
void HeapCreate(Heap* php)
{
    assert(php);
    if(php->size == php->capacity)
    {
        int newCapacity = php->capacity == 0 ? 4 : (php->capacity)*2;
        int* data = (int*) realloc(php->arr,sizeof (int)*newCapacity);
        if(data == NULL)
        {
            perror("malloc fail");
            exit(-1);
        }
        php->arr = data;
        php->capacity = newCapacity;
    }
}

2.5 堆的销毁

//堆的销毁
void HeapDestroy(Heap* php)
{
    assert(php);
    free(php->arr);
    php->arr = NULL;
    php->size = 0;
    php->capacity = 0;
}

2.6 堆的插入

在插入这里我们就要建堆了,但是由于我们的数据是顺序插入的,所以没有办法进行向下调整,这里使用向上调整的方法,原理都是一样的,向上调整就要保证插入的节点以上是堆。

数据结构之堆的实现(图解➕源代码),数据结构,算法文章来源地址https://www.toymoban.com/news/detail-742485.html

void Swap(int* x,int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

//建立大堆,向上调整
void AdjustUp(int* arr,int child)
{
    int parent = (child-1)/2;
    while (child > 0)
    {
        if(arr[child] > arr[parent])
        {
            Swap(&arr[child],&arr[parent]);
            child = parent;
            parent = (child-1)/2;
        }
        else
            break;
    }
}
//堆的插入
void HeapPush(Heap* php,int x)
{
    HeapCreate(php);
    php->arr[php->size] = x;
    php->size++;
    //建立大堆
    AdjustUp(php->arr,php->size-1);
}

2.7 删除根节点


void Swap(int* x,int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

//建立大堆,向下调整
void AdjustDown(int*arr,int parent,int size)
{
    int child = parent*2 + 1;
    while (child < size)
    {
        if(child + 1 < size && arr[child] > arr[child+1])
        {
            child = child + 1;
        }
        if(arr[child] < arr[parent])
        {
            Swap(&arr[child],&arr[parent]);
            parent = child;
            child = parent*2 + 1;
        }
        else
            break;
    }
}
//堆的删除
void HeapPop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    Swap(&php->arr[0],&php->arr[php->size-1]);
    php->size--;
    AdjustDown(php->arr,0,php->size);
}

2.8 取堆顶的数据

//堆的根节点
int HeapTop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    return php->arr[0];
}

2.9 判断堆是否为空

//判断堆是否为空
bool HeapEmpty(Heap* php)
{
    assert(php);
    return php->size == 0;
}

2.10 堆的数据个数

//堆的节点个数
int HeapSize(Heap* php)
{
    assert(php);
    return php->size;
}

到了这里,关于数据结构之堆的实现(图解➕源代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:手撕图解堆的实现和TopK的应用

    要讲到堆,先要说两个关于二叉树的概念 满二叉树:一个二叉树如果每一层的节点数都是最大值,那么这个二叉树就是满二叉树 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是满二叉树的变形,对于深度为k的树有n个节点的二叉树,当且仅当其每一个节点都与

    2024年02月15日
    浏览(48)
  • 数据结构---手撕图解堆的实现和TopK的应用

    要讲到堆,先要说两个关于二叉树的概念 满二叉树:一个二叉树如果每一层的节点数都是最大值,那么这个二叉树就是满二叉树 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是满二叉树的变形,对于深度为k的树有n个节点的二叉树,当且仅当其每一个节点都与

    2024年02月16日
    浏览(38)
  • 数据结构之队列(源代码➕图解➕习题)

            在学过栈之后,会了解到栈的底层是根据顺序表或者链表来构建的,那么我们今天要学习的队列是否也是基于顺序表和链表呢?那我们直接进入正题吧!         还是跟上节一样,依旧用图解的方式让大家更好的理解概念。         队列: 队列指的是图中黑色边框

    2024年02月06日
    浏览(37)
  • 【数据结构初阶】之堆(C语言实现)

    前言 :在二叉树基础篇我们提到了二叉树的顺序实现,今天让我们来学习一下特殊的二叉树———堆的相关知识。 📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月

    2024年04月09日
    浏览(80)
  • 数据结构:堆的实现

    如果有一个关键码的集合 K = { k1 ,k2 ,k3 ,…,kn },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并且 k(i)  k(i*2+1) 和 k(i)  k(i*2+2), i = 0 , 1 , 2…,则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小

    2024年02月13日
    浏览(33)
  • 数据结构---堆的实现

    前言 一、什么是堆? 二、 堆的实现 1. 堆的结构  2. 接口实现 总结 堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。 现实中我们通常把 堆(一种二叉树) 使用 顺序结构的数组 来存储, 大根堆 :根节

    2024年02月02日
    浏览(35)
  • 数据结构—小堆的实现

    前言:前面我们已经学习了二叉树,今天我们来学习堆,堆也是一个二叉树,堆有大堆有小堆,大堆父节点大于子节点,小堆父节点总小于子节点,我们在学习C语言的时候也有一个堆的概念,那个堆是操作系统中的堆,与我们今天所学的堆全然不同。我们就来实现下小堆。

    2024年02月05日
    浏览(33)
  • 数据结构:堆的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 当一颗完全二叉树用顺序表来存储时,其被称为堆。 堆总是一棵完全二叉树 堆的某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值 其可以被用来解决top k 问题 或 堆排序 下面就是要实现的堆的功能 重点在

    2024年02月13日
    浏览(35)
  • 数据结构——二叉树(堆的实现)

    目录   树概念及结构 树的相关概念 树的表示  二叉树的概念及结构   堆 堆的实现   结构体建立 初始化   添加元素  打印堆  删除堆首元素  返回首元素  判断是否为空 空间销毁  刷题找工作的好网站——牛客网 牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,

    2024年02月11日
    浏览(42)
  • 【数据结构】堆的实现及应用

    简单不先于复杂,而是在复杂之后 。 1.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系

    2024年02月21日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包