我的编程空间,编程开发者的网络收藏夹
学习永远不晚

C语言实现大顶堆的示例代码

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

C语言实现大顶堆的示例代码

堆的实现

1.堆结构

逻辑结构上类似于 一棵 “树”

2.堆的种类

大顶堆结构: 一种特殊的树:其每个子节点均比母节点要小

小顶堆结构: 同理:其每个子节点均比母节点要大

结构图示:

3.大顶堆代码实现

这里实现堆 用循序表的方式

①初始化:

typedef int Heaptype;
 
typedef struct Heap
{
    Heaptype* head;   
    int size;         //记录堆总容量 
    int capacity;     //记录当前数据总个数
}Heap;
 
//堆的初始化
void Heap_Init(Heap* pphead)
{
    assert(pphead);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

②插入数据:

实现细节:数据在插入的同时,要进行数据结构的调整,使树顶始终保持最大数

如果新插入节点比母节点大的话,要进行交换 ,因此将这个调整结构的环节独立出来

即:“向上调整”。

 向上调整:因为插入数据时:新数据默认储存在顺序表尾,因此其逻辑上是在堆的底部,

所以,当新数据比母节点大时,它将与逻辑上处于其上方的母节点交换,称为

向上调整。

注:向上调整有时不止调整一次 ,还有可能调整多次,直到每个节点都在其相应位置 。

流程图解:

大顶堆插入流程

细节点:因为数据是以顺序表的方式储存,所以子节点的下标与母节点的下标符合

公式:parent = (child - 1)/2 ;(按照此公式带入计算就理解了) 

//向上调整
void adjust_up(Heap* pphead)
{
    int child = pphead->capacity;
    int parent = (child - 1) / 2;
    for (; pphead->head[parent] < pphead->head[child];)//判断是否符合大顶堆
    {
        swap(&(pphead->head[parent]),&(pphead->head[child]));//进行交换
        child = parent;
        parent = (child - 1) / 2;
    }
}
 
//插入数据
void Heap_push(Heap* pphead, Heaptype data)
{
    assert(pphead);
    //判断是否满容量并扩容
    Heap_realloc(pphead);
    pphead->head[pphead->capacity] = data;
    //向上调整
    adjust_up(pphead);
    pphead->capacity++;
}

③删除数据:为了避免因为直接删除头部数据导致整个堆的结构打乱,

这里先将头部数据与尾数据交换,然后将尾部数据删除,接着使用“向下调整”,即:将换上来的顶部数据向下与其子节点比较调整,直至符合大顶堆结构为止。

注:1.大顶堆向下调整时,母节点要与两个子节点中较大的一个交换 ,因此要比较一下。

2.这里下标的计算公式为:左孩子:child = (parent * 2) + 1

右孩子:child = (parent * 2) + 2

3.计算孩子下标时要避免越界,避免将母节点与不属于堆中的数据比较。

//删除数据
void Heap_pop(Heap* pphead)
{
    assert(pphead);
    assert(pphead->capacity > 0);      //防止堆为空
    //将顶部数据与尾部数据交换
    swap(&(pphead->head[0]),&( pphead->head[pphead->capacity-1]));
    pphead->capacity--;
    //向下调整
    adjust_down(pphead,0);
}
 
//向下调整
void Adjust_down(int* a, int size, int parent)
{
    assert(a);
    for (int child = parent * 2 + 1; child <= size; child = parent * 2 + 1)
    {
        //默认用左孩纸与母节点比较,如果右孩纸比左孩纸大且不越界则交换
        if (a[child] > a[child + 1] && child + 1 <= size)
            child = child + 1;
        //比较孩纸和母节点
        if (a[child] < a[parent])
        {
            int temp = a[child];
            a[child] = a[parent];
            a[parent] = temp;
        }
        //向下继续比较
        parent = child;
    }
}

④扩容 || 判空 || 取顶数据 || 销毁堆

//判断是否扩容
void Heap_realloc(Heap* pphead)
{
    assert(pphead);
    if (pphead->size == pphead->capacity)
    {
        Heaptype Newsize = (pphead->size == 0) ? 4 : (pphead->size * 2);
        Heaptype* Newhead = (Heaptype*)realloc(pphead->head,sizeof(Heaptype) * Newsize);
        if (Newhead == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        pphead->head = Newhead;
        pphead->size = Newsize;
    }
}
 
//判断堆是否为空
bool Heap_Empty(Heap* pphead)
{
    if (pphead->capacity)
        return false;
    return true;
}
//取对顶数据
Heaptype Heap_top(Heap* pphead)
{
    return pphead->head[0];
}
//销毁堆
void Heap_Destory(Heap* pphead)
{
    assert(pphead);
    free(pphead->head);
    pphead->head = NULL;
    pphead->size = 0;
    pphead->capacity = 0;
}

以上就是C语言实现大顶堆的示例代码的详细内容,更多关于C语言大顶堆的资料请关注编程网其它相关文章!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

C语言实现大顶堆的示例代码

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

C语言实现堆的简单操作的示例代码

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。本文介绍了C语言中堆的一些简单操作,需要的可以参考一下
2022-11-13

c++实现堆排序的示例代码

本文主要介绍了c++实现堆排序的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
2023-02-02

C语言实现通讯录的示例代码

这篇文章主要为大家详细介绍了如何录音C语言实现一个简单的通讯录,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
2022-11-13

C语言模拟实现memmove的示例代码

memmove函数用于拷贝字节,如果目标区域和源区域有重叠的话,memmove能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中,但复制后源内容会被更改。本文主要介绍了C语言模拟实现memmove的示例代码,需要的可以参考一下
2022-12-29

C语言实现数独程序的示例代码

数独是源自瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。本文将利用C语言实现数独程序,感兴趣的小伙伴可以跟随小编一起学习一下
2023-03-03

C语言实现2D赛车游戏的示例代码

此游戏是《2D赛车》的”魔改版“——2.5D双人赛车!原作实现了2D视角的赛车游戏,但是我觉得不够真实、操纵感不强,故挤出数个周末完成了这个”魔改版“,实现了第一人称的视角,希望大家喜欢
2022-12-28

C语言实现动态顺序表的示例代码

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。顺序表一般分为静态顺序表和动态顺序表,本文主要和大家介绍的是动态顺序表的实现,需要的可以参考一下
2022-11-13

C语言实现扫雷小游戏的示例代码

这篇文中主要为大家详细介绍了如何利用C语言实现经典的扫雷小游戏。扫雷小游戏主要是利用字符数组、循环语句和函数实现,感兴趣的小伙伴可以了解一下
2022-11-13

C语言实现绘制绕线画的示例代码

绕线画简单点来说,就是在木板上钉一圈钉子,通过绕线进行构图,最终呈现出一幅图像。本文将用C语言实现这一效果,感兴趣的小伙伴可以尝试一下
2022-11-13

C语言实现三子棋游戏的示例代码

今天我们将会用C语言实现三子棋。所谓三子棋,就是三行三列的棋盘,玩家可以和电脑下棋,率先连成三个的获胜。话不多说,我们开始吧
2022-11-13

C语言实现音乐播放器的示例代码

这篇文章主要和大家分享了一个C语言的小DEMO,可以实现音乐播放器功能,文中的示例代码讲解详细,具有一定的借鉴价值,需要的可以参考一下
2023-02-26

C语言实现经典排序算法的示例代码

这篇文章主要为大家详细介绍了如何利用C语言实现经典排序算法中的冒泡排序、选择排序、插入排序、希尔排序,文中的示例代码讲解详细,需要的可以参考一下
2022-11-13

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录