AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构与算法】二叉树——堆的增删查改

2023-02-24 117
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构与算法】二叉树——堆的增删查改
🌹作者:云小逸
📝个人主页: 云小扬的主页
📝码云： 云小扬 (YunXiaoYang003) - Gitee.com
🤟motto:要敢于一个人默默的面对自己， ==强大自己才是核心==。不要等到什么都没有了，才下定决心去做。种一颗树，最好的时间是十年前，其次就是现在！学会自己和解，与过去和解，努力爱自己。==希望春天来之前，我们一起面朝大海，春暖花开==！🤟
👏专栏：C语言初阶👏专栏：C语言进阶👏专栏：数据结构和算法👏
👏专栏：C++初阶---👏专栏：C++进阶--👏专栏：Linux学习👏

@TOC

前言

前面我们已经说了关于二叉树的相关概念和二叉树的前、中、后序遍历，今天我们就来学习一下，二叉树的一种形式:堆。
——————————————————————————————
首先先写上几句话：献给坚持创作的我和点开这篇文章希望进步的你

a.这些年我一直提醒自己一件事情，千万不要自己感动自己。大部分人看似的努力，不过是愚蠢导致的。
b.什么熬夜看书到天亮，连续几天只睡几小时，多久没放假了，如果这些东西也值得夸耀，那么富士康流水线上任何一个人都比你努力多了。人难免天生有自怜的情绪，唯有时刻保持清醒，才能看清真正的价值在哪里。
c.大部分人在二三十岁上就死去了，因为过了这个年龄，他们只是自己的影子，此后的余生则是在模仿自己中度过。日复一日，更机械，更装腔作势地重复他们在有生之年的所作所为，所思所想，所爱所恨。

1.堆的基本概念和结构：

a.堆的概念

二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。
最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

b.堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

c.堆的结构

物理上：一维数组
逻辑上:完全二叉树
小根堆

2.堆的操作

注：插入删除不可以改变堆的性质，即大堆或小堆，本篇代码是以小堆为例子！！！

（1）堆的建立

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

（2）堆的初始化

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

（3）堆的插入

思想：向上调整算法

逻辑上：

在这里插入图片描述

物理上：

在这里插入图片描述

交换函数：

void HeapSwap(HPDataType* pa,HPDataType* pb)
{
    HPDataType temp = *pa;
    *pa = *pb;
    *pb = temp;
}

向上调整算法函数

void AdjustUp(HPDataType* a, size_t child)
{
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])
        {
            HeapSwap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}

插入函数

void HeapPush(HP* php, HPDataType x)
{
    assert(php);//插入之前要想考虑是否要扩容！！！
    if (php->size == php->capacity)
    {
        size_t newnode = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* temp = realloc(php->capacity, sizeof(HPDataType) * newnode);
        if (temp == NULL)
        {
            printf("realloc failed!\n");
            exit(-1);
        }
        php->a = temp;
        php->capacity = newnode;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}

在这里插入图片描述

（4）堆的删除

思想：向下调整法

在这里插入图片描述

向下调整函数：

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

删除函数

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

在这里插入图片描述

（5）判断堆是否为空

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

（6）求堆的长度

size_t HeapSize(HP* php)
{
    assert(php);
    return php->size;
}

在这里插入图片描述

（7）返回堆顶的值

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

在这里插入图片描述

（8）销毁堆

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

（9）遍历堆

void HeapPrint(HP* php)
{
    assert(php);
    size_t i = 0;
    for (i = 0; i < php->size; i++)
    {
        printf("%d  ", php->a[0]);
    }
    printf("\n");
}

完整源码：

Heap.h文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
    HPDataType* a;
    size_t size;
    size_t capacity;
}HP;
void HeapInit(HP* php);
void HeapInit(HP* php);
void HeapSwap(HPDataType* pa, HPDataType* pb);
void AdjustUp(HPDataType* a, size_t child);
void HeapPush(HP* php, HPDataType x);
void AdjustDown(HPDataType* a, size_t size, size_t root);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);
void HeapDestroy(HP* php);
void HeapPrint(HP* php);

Heap.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HeapInit(HP* php)
{
    assert(php);
    php->a = NULL;
    php->capacity = php->size = 0;
}
void HeapSwap(HPDataType* pa,HPDataType* pb)
{
    HPDataType temp = *pa;
    *pa = *pb;
    *pb = temp;
}
void AdjustUp(HPDataType* a, size_t child)
{
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] < a[parent])
        {
            HeapSwap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
            break;
    }
}
void HeapPush(HP* php, HPDataType x)
{
    assert(php);//插入之前要想考虑是否要扩容！！！
    if (php->size == php->capacity)
    {
        size_t newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* temp = realloc(php->a, sizeof(HPDataType) * newcapacity);
        if (temp == NULL)
        {
            printf("realloc failed!\n");
            exit(-1);
        }
        php->a = temp;
        php->capacity = newcapacity;
    }
    php->a[php->size] = x;
    php->size++;
    AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        if (child<size && a[child]>a[child + 1])
        {
            child++;
        }
        if (a[parent] > a[child])
        {
            HeapSwap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
            break;
    }
}
void HeapPop(HP* php)
{
    assert(php);
    assert(php->size);
    HeapSwap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    AdjustDown(php->a, php->size, 0);
}
bool HeapEmpty(HP* php)
{
    assert(php);
    return php->size==0;
}
size_t HeapSize(HP* php)
{
    assert(php);
    return php->size;
}
HPDataType HeapTop(HP* php)
{
    assert(php);
    return php->a[0];
}
void HeapDestroy(HP* php)
{
    assert(php);
    php->a = NULL;
    php->size = php->capacity = 0;
    free(php);
}
void HeapPrint(HP* php)
{
    assert(php);
    size_t i = 0;
    for (i = 0; i < php->size; i++)
    {
        printf("%d  ", php->a[i]);
    }
    printf("\n");
}

test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
int main(void)
{
    HP hp;
    HeapInit(&hp);
    HeapPush(&hp, 1);
    HeapPrint(&hp);
    HeapPush(&hp, 5);
    HeapPrint(&hp);
    HeapPrint(&hp);
    HeapPush(&hp, 0);
    HeapPrint(&hp);
    HeapPush(&hp, 8);
    HeapPrint(&hp);
    HeapPush(&hp, 3);
    HeapPrint(&hp);
    HeapPush(&hp, 9);
    HeapPrint(&hp);
    HeapPop(&hp);
    HeapPrint(&hp);
    HeapPop(&hp);
    HeapPrint(&hp);
    HeapPop(&hp);
    HeapPrint(&hp);
    printf("%d\n", HeapSize(&hp));
    printf("%d", HeapTop(&hp));
    return 0;
    HeapDestroy(&hp);
}

运行结果截图：

在这里插入图片描述

最后

十分感谢你可以耐着性子把它读完和我可以坚持写到这里，送几句话，对你，也对我：

  1. 我的人生是一栋只能建造一次的楼房，我必须让它精确无比，不能有一厘米差池——所以，我太紧张，害怕行差步错。

2.我不想要那种一眼就可以看到死的人生，那种 “我们到底是活了365天，还是活了一天却重复了364遍” 的悲哀，我实在无法想象日复一日的重复一天的人生还有什么意义，我才20岁，人生难道就此再无波澜和际遇？
3.这对我来说依旧可怕，我害怕后果，害怕行差步错，害怕放弃了所有 却依旧失去了她。
4.只问自由，只问盛放，只问深情，只问初心，只问勇敢，无问西东
5.少发脾气。收敛脾气，内心才有元气。不同层次无需讲道理；不同位置无需争辩对错；三观不合无需探讨私事。
6.在感情中及时止损，该说拜拜的人不回头挽留。
7.不刻意满足别人的期待而活着。敢做真实的自己，才有人爱上真实的你。按照自己喜欢的方式去生活，越多对的人会向你靠近。

最后如果觉得我写的还不错，请不要忘记==点赞==✌，==收藏==✌，加==关注==✌哦(｡･ω･｡)

愿我们一起加油，奔向更美好的未来，愿我们从懵懵懂懂的一枚==菜鸟==逐渐成为==大佬==。加油，为自己点赞！
​

​

文章标签：
C++
C语言
Linux
算法
关键词：
数据结构二叉树
数据结构堆
算法堆
数据结构二叉树堆
算法二叉树
云-小逸
目录
相关文章
ephemerals__
|
2天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
32 16
ephemerals__
|
2天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
28 8
java冯坚持
|
22天前
|
缓存 算法 Java
JVM知识体系学习六：JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机（JVM）中的垃圾回收机制，包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程，以及不同垃圾回收器的工作原理和参数设置。
java冯坚持
45 4
JVM知识体系学习六：JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
mao29955
|
1天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些？
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法，在许多领域都有着不可或缺的应用，它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展，二叉树遍历算法也在不断地被优化和扩展，以适应新的应用场景和需求。
mao29955
4 0
神明木佑
|
23天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
61 1
java冯坚持
|
25天前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
16 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
25天前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
15 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
阿客不是客
|
24天前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
17 0
简简单单做算法
|
12天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中，通过游戏理论优化动态频谱访问，提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本：Matlab 2022a。完整代码包含详细中文注释和操作视频。
简简单单做算法
30 2
软件算法开发
|
9天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术，通过遗传算法优化水印嵌入参数，提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试，展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化，有效提升了水印技术的应用价值。
软件算法开发
28 6

热门文章

最新文章

  • 1
    栈的数组实现_JAVA描述《数据结构与算法分析》
  • 2
    数据结构与算法：链表（源码）！
  • 3
    20120919-二叉树 数据结构《数据结构与算法分析》
  • 4
    JS数据结构与算法-链表
  • 5
    数据结构与算法--链表
  • 6
    JS数据结构与算法-队列
  • 7
    数据结构与算法之《单链表》详解
  • 8
    每周一练 之 数据结构与算法（Tree）
  • 9
    【数据结构与算法】—— * 深度优先搜索入门 *
  • 10
    JavaScript 数据结构与算法 之 队列和双端队列
  • 1
    【算法与数据结构】二叉树（前中后）序遍历2
    38
  • 2
    Machine Learning机器学习之决策树算法 Decision Tree（附Python代码）
    304
  • 3
    从动态规划到贪心算法：最长递增子序列问题的方法全解析
    285
  • 4
    【数据结构】八大排序之计数排序算法
    41
  • 5
    【数据结构】八大排序之归并排序算法
    46
  • 6
    【数据结构】八大排序之快速排序算法
    109
  • 7
    深入理解InnoDB索引数据结构和算法
    326
  • 8
    Java入门高频考查算法逻辑基础知识3-编程篇（超详细18题1.8万字参考编程实现）
    85
  • 9
    sklearn应用线性回归算法
    78
  • 10
    深度思考：雪花算法snowflake分布式id生成原理详解
    1573

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 【云栖精选7月刊】抛开晦涩的算法、模型，让我们来谈谈互联网架构
  • 聚星台—客户运营核心大数据 与算法技术
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 推荐系统入门之使用ALS算法实现打分预测
  • 欧拉图的构造性证明与算法实现
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 使用Swing算法实现商品推荐
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月