数据结构——二叉树的顺序存储(堆)(C++实现)

数据结构——二叉树的顺序存储(堆)(C++实现)

  • 二叉树可以顺序存储的前提
  • 堆的定义
  • 堆的分类
    • 大根堆
    • 小根堆
  • 整体结构把握
  • 两种调整算法
    • 向上调整算法
      • 递归版本
    • 非递归版本
    • 向下调整算法
    • 非递归版本
  • 向上调整算法和向下调整算法的比较

我们接着来看二叉树:

二叉树可以顺序存储的前提

完全二叉树完全符合顺序存储的前提:

完全二叉树:顺序存储二叉树最适合应用于完全二叉树。完全二叉树是一种特殊的二叉树,除最后一层外,每一层都被完全填满,并且所有结点尽可能集中在左边。由于其结构特性,完全二叉树的结点与数组下标之间存在着直接的数学映射关系,**使得每个结点可以按照固定规则(如左孩子为2i,右孩子为2i+1)**在数组中找到其相应的位置。这种映射保证了数组的存储空间得以充分利用,没有浪费。

顺序存储的二叉树我们称为

堆的定义

堆是一种特殊的树形数据结构,通常以数组的形式进行顺序存储。堆具有以下关键性质:

  1. 完全二叉树结构
    堆是一个完全二叉树或近乎完全二叉树。这意味着除了可能的最后一层外,其他各层都是完全填充的,并且最后一层的所有结点都尽可能靠左排列。这种结构非常适合用数组来表示,因为完全二叉树的结点与数组下标之间存在直接的数学映射关系,使得每个结点可以高效地通过下标访问。

  2. 堆序性质
    堆分为两种主要类型:最大堆和最小堆。无论哪种类型,堆都遵循特定的堆序性质:

  • 大根堆:每个结点的值都大于或等于其子结点的值。即对于任意结点 i,其值 A[i] 大于等于其左孩子 A[2*i+1] 和右孩子 A[2*i+2] 的值。
  • 小根堆:每个结点的值都小于或等于其子结点的值。即对于任意结点 i,其值 A[i] 小于等于其左孩子 A[2*i+1] 和右孩子 A[2*i+2] 的值。

由于堆的完全二叉树特性和堆序性质,它非常适合使用数组进行顺序存储。具体来说:

  • 数组下标与结点关系

假设数组 A 存储了一个堆,根结点位于下标 0。那么对于任一结点 i,其左孩子、右孩子的下标分别为 2*i + 12*i + 2,而其父结点的下标为 (i - 1) // 2(向下取整)。这种固定的下标关系使得在数组中进行堆的操作(如插入、删除、调整等)变得非常直观和高效。

  • 空间利用率

由于堆是完全或近乎完全二叉树,其存储在数组中时空间利用率较高。即使不是严格的完全二叉树,只要整体结构相对平衡,数组中的空闲位置也相对较少,不会造成过多的存储浪费。

  • 操作复杂度

堆的常见操作(如插入、删除堆顶元素、调整堆等)的时间复杂度通常为 O(log n),这是因为堆的高度与结点数成对数关系。数组的随机访问特性使得这些操作能够在常数时间内定位到相关结点,然后通过递归或迭代方式进行堆结构调整。

因此,堆作为一类满足特定条件的二叉树,其完全二叉树特性、堆序性质以及高效的操作性能,使其非常适合采用数组进行顺序存储。堆常用于实现优先队列、求解Top-K问题、堆排序算法等场景。

堆的分类

大根堆

大根堆是一种特殊的二叉堆,其中每个节点的值都大于或等于其子节点的值。具体地说,对于大根堆中的任意节点 i,其值 A[i] 大于等于其左孩子 A[2*i+1] 和右孩子A[2*i+2]的值。根节点(数组下标为1或0,取决于实现)总是包含堆中的最大值。大根堆常用于实现优先队列,其中队首元素始终为当前最大的元素。
在这里插入图片描述

小根堆

小根堆也是一种特殊的二叉堆,其中每个节点的值都小于或等于其子节点的值。对于小根堆中的任意节点 i,其值 A[i] 小于等于其左孩子 A[2*i+1] 和右孩子 A[2*i+2] 的值。根节点(同样为数组下标为1或0)始终包含堆中的最小值。小根堆同样适用于优先队列的场景,但此时队首元素为当前最小的元素。
在这里插入图片描述

整体结构把握

我们这里用vector作为底层容器来存储数据,这些数据按照顺序排放:

#pragma once
#include<iostream>
#include<vector>template<class T>
//堆的定义
class Heap
{
public:Heap():_size(0){_data.resize(10);}Heap(const size_t& size):_size(0){_data.resize(size + 1);}//插入void insert(const T& data){if(_size > _data.capacity()){_data.resize(2 * _data.size());}_data[++_size] = data;}//是否为空bool empty(){return _size == 0;}//打印堆void printHeap(){for(int i = 1; i < _size + 1; i++){std::cout<< _data[i] << " ";}std::cout << std::endl;}private:std::vector<T> _data; //存放数据size_t _size; //当前数据个数
};

这里注意一下,我的一个数据并没有放在0号位置,而是放在了1号位置,这样方便我们寻找父节点:
在这里插入图片描述
我们可以先测试一下:

#include"heap.h"int main()
{Heap<int> heap;heap.insert(12);heap.insert(23);heap.insert(1);heap.insert(0);heap.insert(24);heap.insert(4);heap.insert(188);heap.insert(9);heap.insert(58);heap.printHeap();return 0;
}

在这里插入图片描述

两种调整算法

向上调整算法

向上调整算法的核心是把每一个结点都当做孩子,去跟自己的父亲比较,如果比自己的父亲大(或者小)交交换数据
在这里插入图片描述

递归版本

递归版本比较好想,我只管我自己和父亲的比较,比较完之后,继续向上比较:

// 向上调整函数(以小根堆为例)
// 输入参数:index - 需要进行调整的子节点索引
void sifUpHeap(const size_t& index)
{// 如果索引小于 1,说明已经到达根节点或无效索引,无需继续调整,直接返回if (index < 1){return;}// 获取当前子节点的父节点索引size_t parentIndex = Parent(index);// 如果子节点索引大于 1(即不是根节点),并且子节点的值小于其父节点的值// 则交换两者,确保父节点的值小于其子节点的值(小根堆性质)if (index > 1 && _data[parentIndex] > _data[index]){std::swap(_data[parentIndex], _data[index]);// 对交换后的新父节点(原子节点)继续进行向上调整,确保整棵子树满足小根堆性质sifUpHeap(parentIndex);}// 返回,完成当前节点的向上调整过程return;
}

但是我们这样只是完成了一个数据的调整,我们要所有的数据进行调整:

    //向上调整算法(以小根堆为例)void sifUpHeap(const size_t& index){if (index < 1){return;}if(index > 1 && _data[Parent(index)] > _data[index]){std::swap(_data[Parent(index)],_data[index]);//接着向上sifUpHeap(Parent(index));}return;}//调整为小根堆void ToMinHeap(){for(int i = 1; i < _size + 1; i++){sifUpHeap(i);}}

在这里插入图片描述

非递归版本

我们也可以不用递归,使用迭代来完成:

// 向上调整函数(非递归版本,以小根堆为例)
// 输入参数:child - 需要进行调整的子节点索引
void sifUpHeap_non(size_t child)
{// 计算当前子节点的父节点索引size_t parent = child / 2;// 循环迭代,直到子节点成为根节点或已满足小根堆性质while (child > 1){// 如果子节点的值小于其父节点的值// 则交换两者,确保父节点的值小于其子节点的值(小根堆性质)if (_data[Parent(child)] > _data[child]){std::swap(_data[Parent(child)], _data[child]);// 更新子节点索引为交换后的父节点索引,准备对新的子节点进行下一轮比较child = parent;// 重新计算父节点索引parent = child / 2;}else{// 子节点已满足小根堆性质,跳出循环,结束调整break;}}
}//调整为小根堆void ToMinHeap(){for(int i = 1; i < _size + 1; i++){sifUpHeap_non(i);}}

向下调整算法

向下调整算法是把所有结点当做父亲结点,去和自己的孩子结点比较,看哪个孩子结点比自己大或小,就交换
在这里插入图片描述向下调整算法有个条件:左右子树必须为堆,因为这个特性,我们向下调整算法得从最后一个有孩子的双亲结点开始:

// 下降调整函数(以小根堆为例)
// 输入参数:index - 需要进行调整的父节点索引
void sifDownHeap(const size_t& index)
{// 计算当前父节点的左孩子索引size_t leftchild = LeftChild(index);// 如果左孩子索引超出了堆的有效范围(即不存在左孩子),说明无需调整,直接返回if (leftchild > _size){return; // 超出范围,无需调整}// 初始化 "miner" 为当前父节点的左孩子索引// "miner" 用于记录待调整子节点中值最小的那个的索引int miner = leftchild;// 比较左孩子与右孩子(如果存在)的值,确定哪个子节点的值更小// 如果右孩子存在且其值小于左孩子,更新 "miner" 为右孩子索引if (index < _size + 1 && _data[leftchild] > _data[leftchild + 1]){miner++;}// 如果当前父节点的值大于其最小子节点(即 "miner" 所指向的子节点)的值// 则交换两者,确保父节点的值小于其子节点的值(小根堆性质)if (_data[miner] < _data[index]){std::swap(_data[miner], _data[index]);// 对交换后的新父节点(原子节点)继续进行向下调整,确保整棵子树满足小根堆性质sifDownHeap(miner);}// 返回,完成当前节点的向下调整过程return;
}//调整为小根堆void ToMinHeap(){// for(int i = 1; i < _size + 1; i++)// {//     sifUpHeap_non(i);// }for(int i = _size / 2 ; i >=1 ; i--) //从最后一个父节点结点开始调整{sifDownHeap(i);}}

在这里插入图片描述

非递归版本

我们也可以用非递归的方式实现:

// 下降调整函数(以小根堆为例)
// 输入参数:parent - 需要进行调整的父节点索引
void sifDownHeap_non(size_t parent)
{// 计算当前父节点的左孩子索引,假定左孩子为待调整子节点中值最小的一个int child = LeftChild(parent);// 循环迭代,直到越界while (child < _size + 1){// 如果右孩子存在且其值小于左孩子,更新 "child" 为右孩子索引// 保持 "child" 指向待调整子节点中值最小的那个if (parent + 1 < _size + 1 && _data[child] > _data[child + 1]){child++;}// 如果当前父节点的值大于其最小子节点(即 "child" 所指向的子节点)的值// 则交换两者,确保父节点的值小于其子节点的值(小根堆性质)if (_data[parent] > _data[child]){std::swap(_data[parent], _data[child]);// 更新父节点索引为交换后的子节点索引,准备对新的子节点进行下一轮比较parent = child;// 重新计算子节点索引,从新的父节点开始child = LeftChild(parent);}else{// 子节点已满足小根堆性质,跳出循环,结束调整break;}}
}//调整为小根堆void ToMinHeap(){// for(int i = 1; i < _size + 1; i++)// {//     sifUpHeap(i);// }for(int i = _size / 2 ; i >=1 ; i--) //从最后一个结点开始调整{sifDownHeap_non(i);}}

在这里插入图片描述

向上调整算法和向下调整算法的比较

向上调整算法(Sift Up)和向下调整算法(Sift Down)是堆数据结构中常用的两种调整方法,它们各有特点和适用场景,无法简单地说哪个更优秀。选择使用哪种调整方法取决于具体的堆操作需求和上下文。下面分别介绍两者的特性及适用场景:

向上调整算法(Sift Up)

  • 用途:通常用于将新插入的元素或被修改的元素调整到堆中的正确位置,使其满足堆性质(大根堆或小根堆)。例如,在插入新元素后,将其放在堆末尾,然后从该位置开始向上调整,确保新元素及其路径上的所有节点满足堆性质。
  • 特点:从堆底部(新元素所在位置或被修改元素所在位置)开始,逐层向上比较父节点与子节点的值,若子节点值更适合堆顶(对于大根堆,子节点值更大;对于小根堆,子节点值更小),则交换二者,直至子节点成为堆顶或已满足堆性质。
  • 优点
  • 适用于插入操作和单元素修改后的调整,因为新元素或被修改元素的初始位置已知,可以直接从该位置开始调整。
  • 调整过程中涉及的节点数量相对较少,时间复杂度为 O(log n),效率较高。
  • 缺点
  • 不适用于堆顶元素被删除后的调整,因为此时需要重新确定堆顶元素,且可能需要对多个子节点进行比较和调整。

向下调整算法(Sift Down)

  • 用途:通常用于删除堆顶元素后重新调整堆,或在构建堆的过程中对整个堆进行调整。例如,在删除堆顶元素后,将堆末尾元素移至堆顶,然后从堆顶开始向下调整,确保所有节点满足堆性质。
  • 特点:从堆顶开始,逐层向下比较父节点与子节点的值,若父节点值更适合堆底(对于大根堆,父节点值更小;对于小根堆,父节点值更大),则交换二者,直至父节点成为堆底或已满足堆性质。
  • 优点
  • 适用于堆顶元素被删除后的调整,因为此时堆顶元素已知,可以直接从该位置开始调整。
  • 在构建堆的过程中,可以从最后一个非叶子节点开始逐个进行向下调整,确保整个堆满足堆性质。
  • 缺点
  • 对于插入操作或单元素修改后的调整,可能需要遍历到堆底才能找到新元素或被修改元素的最终位置,调整过程中涉及的节点数量可能较多。

综上所述,向上调整算法和向下调整算法各有优势,适用于不同的堆操作场景。在实际应用中,根据具体需求选择合适的调整方法,或者结合使用这两种方法,可以有效维护堆数据结构的性质,确保堆操作的高效性。因此,不能简单地说哪个更优秀,而应视具体情况灵活选用。

如果大家阅读完之后还是比较迷糊的话,可以点击这里,这里是我之前写的堆的博客,介绍的更为详细:

https://blog.csdn.net/qq_67693066/article/details/131544172

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/315018.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

5、Flink事件时间之Watermark详解

1&#xff09;生成 Watermark 1.Watermark 策略简介 为了使用事件时间语义&#xff0c;Flink 应用程序需要知道事件时间戳对应的字段&#xff0c;即数据流中的每个元素都需要拥有可分配的事件时间戳。 通过使用 TimestampAssigner API 从元素中的某个字段去访问/提取时间戳。…

STM32之串口中断接收丢失数据

五六年没搞STM32了&#xff0c;这个项目一切都挺顺利&#xff0c;万万没想到被串口接收中断恶心到了。遇到的问题很奇怪 HAL_UART_Receive_IT(&huart1, &rx_buffer[rx_index], LCD_UART_LEN); 这个代码中 LCD_UART_LEN1的时候&#xff0c;接收过来的数据&#xff0c;数…

CentOS 9 (stream) 安装 nginx

1.我们直接使用安装命令 dnf install nginx 2.安装完成后启动nginx服务 # 启动 systemctl start nginx # 设置开机自启动 systemctl enable nginx# 重启 systemctl restart nginx# 查看状态 systemctl status nginx# 停止服务 systemctl stop nginx 3.查看版本确认安装成功…

Taro引入echarts【兼容多端小程序(飞书/微信/支付宝小程序)】

近期接到公司新需求&#xff0c;开发飞书小程序&#xff0c;并且原型中含有大量的图表&#xff0c;本想使用飞书内置图表组件 —— chart-space&#xff0c;但官方表示已经停止维护了&#xff0c;无奈之下&#xff0c;只能另寻他路&#xff0c;于是乎&#xff0c;图表之王&…

Apollo 7周年大会:百度智能驾驶的展望与未来

本心、输入输出、结果 文章目录 Apollo 7周年大会&#xff1a;百度智能驾驶的展望与未来前言百度集团副总裁、智能驾驶事业群组总裁王云鹏发言 直播回放大会相关内容先了解 Apollo&#xfeff;开放平台 9.0架构图 发布产品Apollo 定义自己对于智能化的认知百度集团副总裁 王云鹏…

Vue入门到关门之Vue介绍与使用

一、vue框架介绍 1、什么是Vue&#xff1f; Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是&#xff0c;Vue 被设计为可以自底向上逐层应用。Vue 的核心库只关注视图层&#xff0c;不仅易于上手&#xff0c;还便于与…

1、Flink DataStreamAPI 概述(上)

一、DataStream API 1、概述 1&#xff09;Flink程序剖析 1.Flink程序组成 a&#xff09;Flink程序基本组成 获取一个执行环境&#xff08;execution environment&#xff09;&#xff1b;加载/创建初始数据&#xff1b;指定数据相关的转换&#xff1b;指定计算结果的存储…

图像处理的魔法师:Pillow 库探秘

文章目录 图像处理的魔法师&#xff1a;Pillow 库探秘第一部分&#xff1a;背景介绍第二部分&#xff1a;库是什么&#xff1f;第三部分&#xff1a;如何安装这个库&#xff1f;第四部分&#xff1a;库函数使用方法第五部分&#xff1a;场景应用第六部分&#xff1a;常见Bug及解…

字符串类型漏洞之updatexml函数盲注

UPDATEXML 是 MySQL 数据库中的一个函数&#xff0c;它用于对 XML 文档数据进行修改和查询。然而&#xff0c;当它被不当地使用或与恶意输入结合时&#xff0c;它可能成为 SQL 注入攻击的一部分&#xff0c;从而暴露敏感信息或导致其他安全漏洞。 在 SQL 注入攻击中&#xff0…

Prompt Engineering,提示工程

什么是提示工程&#xff1f; 提示工程也叫【指令工程】。 Prompt发送给大模型的指令。比如[讲个笑话]、[用Python编个贪吃蛇游戏]、[给男/女朋友写情书]等看起来简单&#xff0c;但上手简单精通难 [Propmpt]是AGI时代的[编程语言][Propmpt]是AGI时代的[软件工程][提示工程]是…

【Unity动画系统】详解Root Motion动画在Unity中的应用(一)

Root Motion动画与普通动画的区别 普通动画&#xff1a;动画文件里记录的是物体的绝对坐标和方向&#xff0c;在播放动画时&#xff0c;Unity会根据Animation中记录的值&#xff0c;直接修改游戏对象的坐标和方向&#xff0c;每一帧的坐标和方向都是通过插值计算得出来的&…

网工学习云计算HCIE感受如何?

作为一名网工&#xff0c;我经常会在各种网络论坛里查询搜索一些网络技术资料&#xff0c;以及跟论坛里的网友交流讨论平时在工作、学习中遇到的问题、故障&#xff0c;因此也经常能在论坛的首页看到誉天的宣传信息。机缘巧合之下关注了誉天的B站号&#xff0c;自从关注了誉天的…

李沐64_注意力机制——自学笔记

注意力机制 1.卷积、全连接和池化层都只考虑不随意线索 2.注意力机制则显示的考虑随意线索 &#xff08;1&#xff09;随意线索倍称之为查询(query) &#xff08;2&#xff09;每个输入是一个值value&#xff0c;和不随意线索key的对 &#xff08;3&#xff09;通过注意力池…

Python 面向对象——6.封装

本章学习链接如下&#xff1a; Python 面向对象——1.基本概念 Python 面向对象——2.类与对象实例属性补充解释&#xff0c;self的作用等 Python 面向对象——3.实例方法&#xff0c;类方法与静态方法 Python 面向对象——4.继承 Python 面向对象——5.多态 1. 封装的基…

每日一练-LeeCode-移除链表元素

题目 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xff1a;[1,2,3,4,5] 示例 2&#xff1a; 输入&a…

【AI开发:音频】二、GPT-SoVITS使用方法和过程中出现的问题(GPU版)

1.FileNotFoundError: [Errno 2] No such file or directory: logs/guanshenxxx/2-name2text-0.txt 这个问题中包含了两个&#xff1a; 第一个&#xff1a;No module named pyopenjtalk 我的电脑出现的就是这个 解决&#xff1a;pip install pyopenjtalk 第二个&#xff1a…

156.25MHz的差分晶体振荡器SG3225VEN

数字经济正焕发出勃勃生机,云计算,大数据,5G和人工智能等新技术的发展给行业带来了新的机遇。无论是在数据中心内部还是在数据中心之间,提供低成本,高速的100/200/400G小型化解决方案都是光模块的发展需求。为了使DSP稳定工作&#xff0c;需要一个小型的封装晶体振荡器来提供参…

13.JAVAEE之HTTP协议

HTTP 最新的版本应该是 HTTP/3.0 目前大规模使用的版本 HTTP/1.1 使用 HTTP 协议的场景 1.浏览器打开网站 (基本上) 2.手机 APP 访问对应的服务器 (大概率) 学习 HTTP 协议, 重点学习 HTTP 的报文格式 前面的 TCP/IP/UDP 和这些不同, HTTP 的报文格式,要分两个部分来看待.请求…

「51媒体」城市推介会,地方旅游推荐,怎么做好媒体宣传

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 城市推介会和地方旅游推荐是城市形象宣传的重要组成部分&#xff0c;通过有效的媒体宣传可以提升城市的知名度和吸引力。&#xff1a; 一&#xff0c;活动内容层面&#xff1a; 突出亮点…

Jenkins CI/CD 持续集成专题四 Jenkins服务器IP更换

一、查看brew 的 services brew services list 二、编辑 homebrew.mxcl.jenkins-lts.plist 将下面的httpListenAddress值修改为自己的ip 服务器&#xff0c;这里我是用的本机的ip 三 、重新启动 jenkins-lts brew services restart jenkins-lts 四 、浏览器访问 http://10.…