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

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

2023-02-24 216
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构与算法】二叉树——堆的增删查改
🌹作者:云小逸
📝个人主页: 云小扬的主页
📝码云： 云小扬 (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
算法
关键词：
算法二叉树
数据结构二叉树
数据结构堆
算法堆
数据结构二叉树堆
云-小逸
目录
相关文章
修己xj
|
8月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
279 10
算法系列之数据结构-二叉树
光明顶阳顶天
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码，实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
光明顶阳顶天
326 64
RossyYan
|
10月前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
294 12
RossyYan
|
10月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
191 10
RossyYan
|
10月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
439 3
小山那边
|
11月前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代，文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用，并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构，每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树，能高效地管理和检索文件。相较于顺序查找，二叉树查找每次比较可排除一半子树，极大提升了查找效率，尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数，展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
小山那边
195 5
三三是该溜子
|
11月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
266 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
LucianaiB
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
LucianaiB
308 4
荔枝科研社
|
1月前
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
荔枝科研社
192 0
哈你真皮
|
1月前
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
哈你真皮
143 2

热门文章

最新文章

  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
  • 2
    率先实现后量子安全算法技术落地上车！阿里云与小鹏汽车签署后量子加密安全合作协议
  • 3
    要不要做算法、大模型备案？看这个流程图就明白了！
  • 4
    【机器学习算法篇】K-近邻算法
  • 5
    别再用均值填充了！MICE算法教你正确处理缺失数据
  • 6
    从零构建短视频推荐系统：双塔算法架构解析与代码实现
  • 7
    DDMA-MIMO雷达多子带相干累积目标检测算法——论文阅读
  • 8
    137_安全强化：输入过滤与水印 - 实现输出水印的检测算法与LLM安全防护最佳实践
  • 9
    《数据之美》：图结构的精妙世界与算法实践
  • 10
    采用蚁群算法对BP神经网络进行优化
  • 1
    232.用栈实现队列，225. 用队列实现栈
    143
  • 2
    栈区的非法访问导致的死循环(x64)
    118
  • 3
    Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
    295
  • 4
    Redis设计与实现——数据结构与对象
    317
  • 5
    快速排序-数据结构与算法
    541
  • 6
    16.1k star! 只需要DDL就能一键生成数据库关系图！开源神器ChartDB让你的数据结构"看得见"
    1605
  • 7
    java实现队列数据结构代码详解
    246
  • 8
    Java 中 .length 的使用方法：深入理解 Java 数据结构中的长度获取机制
    758
  • 9
    线性数据结构详解
    218
  • 10
    为什么要学习数据结构与算法
    190

    • 相关课程

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

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台
    • 下一篇
    oss云网关配置