程序员经验分享-hwhale

【Hello Algorithm】堆和堆排序

2023-10-27

本篇博客简介： 讲解堆和堆排序相关算法

堆

堆的概念

这里注意！！！ 这里说的堆和操作系统里面的堆没有半点关系！！！

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

上面这个就是官方的解释了

但是要是我们用通俗的话来说

就是这样子的

大堆 就是所有的父节点都大于等于子节点的堆

小堆 就是所有的子节点都小于等于父节点的堆

如图

在这里插入图片描述

堆的性质

  1. 堆总是一棵完全的二叉树

  2. 堆中某个节点的值总是不大于或者不小于其父节点的值

什么是完全二叉树呢

它要么是一颗满二叉树 要么它正在变满的路上

堆的表示形式

我们一般使用一个数组来从存储结构上表示一个堆 而堆在逻辑结构上表示一颗二叉树

具体的示例如下

假设我们现在有如下的一个数组

在这里插入图片描述

现在要将其转化为一颗完全二叉树

我们在上文说过一句话 堆要么是一颗满二叉树 要么在变成满二叉树的路上

所以说 我们只要按照满二叉树的形式构造一颗二叉树 到最后构造出来的一定是一颗完全二叉树

而满二叉树每一层的节点格式是确定的 所以说我们从第一层开始 依次拿一个数字 两个 数字 四个数字… 构造即可

在这里插入图片描述

从上面的构造中 我们能发现这样子的一个规律

我们现在假设 i 为数组的下标 那么根据完全二叉树的特征 我们可以得出以下结论

如果i对应的节点左孩子 右孩子 父亲节点存在的话

  • i 对应节点的左孩子节点下标一定是 2*i+1
  • i 对应节点的右孩子节点下标一定是 2*i+2
  • i 对应节点的父节点下标一定是 (i-1)/2

堆的增加

我们假设现在有一个空数组 我们要用这个数组构建出一个大堆

现在依次插入数字 10 8 6 那么形成的逻辑结构如下

在这里插入图片描述

目前二叉树是一个完全二叉树 并且符合大堆的性质

可是如果我们下一个数字插入 12 那么我们就破坏了这个大堆了

插入数字 12 之后就会出现子节点大于父节点的情况 这明显和我们上面讲的大堆的性质不符

在这里插入图片描述

此时为了让我们的大堆继续生效 我们就需要将出问题的节点向上调整

而又根据我们上面将的性质 一个节点通过公式 (i-1)/2 就能够找到它的父节点

之后就是与父节点比大小 如果子节点大就交换它们的位置

在这里插入图片描述

可是我们交换一次之后并不能保证这就是个大堆了 所以说向上调整要一直调整到根节点或者说比较不过父节点为止

在这里插入图片描述

删除堆的最大值

在这里插入图片描述
我们想要删除堆中的一个数据 还要不改变这个堆的结构 这个时候怎么办呢

我们这里给出一种很巧妙的解法

我们先将最前面的元素和最后面的元素交换位置

然后再删除掉堆最后面的元素

之后开始向下调整这个堆

如上图所示

如果说一个堆有 14 个元素 其中下标为7的为止的值被修改成了一个未知的值 我们应该如何修改使得该堆正常

其实思路很简单 它的值变化只有三种可能 变大 变小 不变

不变的情况我们不考虑 如果变大或者变小 其他位置的值是不发生改变的

我们只需要对于该位置执行两个操作

  • 向上调整
  • 向下调整

如果向上调整调用成功 则说明上面的树已经恢复正常了 而下面的树根本就没变 所以说这个堆整体就正常了 我们也不不需要向下调整了

如果我们向上调整之后 这个堆没有变化 那一定说明上面没问题 下面出问题了 此时调用向下调整即可

堆排序

我们C++中是实现了堆这种数据结构的 具体内容可以参考我的这篇博客

此外这篇博客中还详细讲解了 向上调整和向下调整的算法 优先级队列

堆排序的时间复杂度

进行堆插入的过程要调用向上调整函数

我们假设 堆中有N的元素 那么这个堆的逻辑二叉树结构就有LogN层高

所以说我们最多最多要比较LogN次 因为每一次插入的时间复杂度都是LogN

如果我们插入N个数 那么时间复杂度就是 N*LogN了

堆排序思路

如果说现在给我们一个无序的数组 要让我们对于这个数组从小到大排序

那么我们可以构建一个小堆作为中间的数据结构

方法如下

  • 首先将数组中的数组遍历一遍 并且放入到优先级队列中
  • 优先级队列的根节点一定是最小值 所以我们每次拿数据一定保证是比后面值要小的
  • 我们从0下标开始填数据 每次下标加1并且填写根节点的值 直到堆中没有数据为止

时间复杂度为N的建堆方法

我们如果每次都是在最后插入数据 不停向上调整的话 建堆的时间复杂度是趋近于N*LogN的

但是在一定条件下 我们的建堆时间复杂度可以达到 N 需要达到的条件如下

  • 我们要知道数组的大小
  • 我们要知道所有需要插入的数字

建堆思路如下

  • 我们从最后一层最后一个结点开始建堆 使用向下调整的算法
  • 调整完最后一层之后我们继续从上一层的最后一个节点开始 插入数据 使用向下调整的算法
  • 重复上面的步骤

下面是我的笔记分析

在这里插入图片描述

已知一个近乎有序的数组 使用最佳排序方法排序

我们现在已知一个几乎有序的数组 请选择一个合适的排序方法将其排序 并说明时间复杂度是多少

  • 几乎有序的指的是 如果把数组排好序的话 每个元素移动的距离一定不超过K

解决这个问题我们的思路还是使用堆排序

我们假设K值为5

那么我们现在建立一个小堆 堆的大小为6 那么我们可以肯定的说 这个小堆的根节点就是这个数组的最小值

因为这六个数中肯定会有数组的最小值 而我们排序获取了这六个数的最小值 那么该值就一定是数组的最小值了

之后我们数组中的第二小值肯定在第2~7个数字中 我们只需要将数组的后一个元素插入小堆中即可找到

之后按照上面的方法 排一个插一个 排一个插一个

我们一共排了N个数字 每个数字最坏的情况要交换LogK次

所以说 最坏的时间复杂度为 NLogK 当K足够小的时候 时间复杂度可以近似看作NLogK

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法

数据结构

【Hello Algorithm】堆和堆排序 的相关文章

随机推荐

  • C#之删除数据库的数据（删）

    private void button3 Click object sender EventArgs e try string id dataGridView1 SelectedRows 0 Cells 0 Value ToString 获

  • BlocProvider add数据流程

    我们看看往bloc中添加数据流程 以demo为例 void incrementCounter counter BlocProvider of

  • TCP协议的三次握手（为了建立连接）

    TCP协议的三次握手 为了建立连接 第一次握手 客户端 Client 向服务器端 Server 发送连接请求 等待服务器端确认 在这一次 客户端会发送一个含SYN同步标志的 TCP报文 SYN同步报文会指明客户端使用的端口以及TCP连接的初

  • Prometheus-Alertmanager 警报管理器-通知模版

    文章目录 一 通知模版介绍 二 模板中可用的数据结构 1 数据 Data 2 告警 Alert 3 KV 4 方法 三 定义可重用模版 一 通知模版介绍 发送给接收方的通知是通过模板构建的 警报管理器附带默认模板 但也可以自定义它们 为避免

  • AndroidStudio升级问题

    前言 今天开这篇文章记录之后遇到AndroidStudio升级或BUG问题 Android Studio Dolphin 2021 3 1 Patch 1 升级 无法运行项目 Android Studio Dolphin 2021 3 1

  • 【源码+文档】绘制太阳系之C语言

    一 实验任务 绘制出一个太阳系 要求 1 有详细的计算步骤 2 至少包含太阳 地球和月亮 3 用 OpenGL 进行绘制 Bonus 1 用代码实现出可执行的实例 2 绘制出行星的轨道 二 原理和分析 1 OpenGL 材质和光照 Open

  • CSS宽度问题

    一 魔法 为 DOM 设置宽度有哪些方式呢 最常用的是配置width属性 width属性在配置时 也有多种方式 width min width max width 通常当配置了 width 时 不会再配置min width max widt

  • 【华为OD机试真题 C语言】48、 寻找身高相近的小朋友

    文章目录 一 题目 题目描述 输入输出 样例1 二 思路参考 三 代码参考 作者 鲨鱼狼臧 个人博客首页 鲨鱼狼臧 专栏介绍 2023华为OD机试真题 使用C语言进行解答 专栏每篇文章都包括真题 思路参考 代码分析 订阅有问题后续可与博主解

  • 基于深度学习实现以图搜图功能

    前记 深度学习的发展使得在此之前以机器学习为主流算法的相关实现变得简单 而且准确率更高 效果更好 在图像检索这一块儿 目前有谷歌的以图搜图 百度的以图搜图 而百度以图搜图的关键技术叫做 感知哈希算法 这是一个很简单且快速的算法 其原理在于针

  • 滚蛋吧，正则表达式！

    大家好 我是良许 不知道大家有没有被正则表达式支配过的恐惧 看着一行火星文一样的表达式 虽然每一个字符都认识 但放在一起直接就让人蒙圈了 你是不是也有这样的操作 比如你需要使用 电子邮箱正则表达式 首先想到的就是直接百度上搜索一个 然后采用

  • 数据名称：中国家庭追踪调查（CFPS）数据区县码数据描述：162个区县代码，适用于10-20年份，可匹配约85-90%的样本。可依次匹配coutyid-区县行政码code-地级市行政码city-省份

    数据名称 中国家庭追踪调查 CFPS 数据区县码 数据描述 162个区县代码 适用于10 20年份 可匹配约85 90 的样本 可依次匹配coutyid 区县行政码code 地级市行政码city 省份行政码province 从而进行市或县层

  • JAVA线程究竟有几种状态？

    线程状态 线程的状态 在你 度的过程中 你会发现 答案有5种 6种 甚至还有7种的 那么究竟有几种状态 准确答案就是6种 在编译器JDK1 5以后的环境下 打开Thread进入源码看看 A thread state A thread can

  • 关于python类说法正确的是_关于Python的说法正确的是

    判断题 1 5压强是大量分子对器壁碰撞的结果 具有统计意义 单选题 1 10 在常温下有1mol的氢气和1mol的氦气各一瓶 若将它们升高相同的温度 则 单选题 1 8 单选题 2 8 一容积不变的容器内充有一定量的某种理想气体 将该理想气

  • c++中struct构造函数

    构造函数 说白了 就是初始化 具体的打法是这个样子的 struct node 构造函数 node 形参表 内容 例子 struct node node int c x c y z 0 int x y z 当然 他既然作为一个函数 那么在里面

  • Leetcode 11. Container With Most Water

    如何盛最大的水 数组代表高度 盛的水量V min height left height right 底部的长度 right left 双指针解决这个问题 从左边 右边不断逼近 逐渐取得最大值 如何进行更新 不断进行更新逼近 因为决定的是he

  • portainer使用二进制文件安装

    一 安装portainer 1 1 查看portainer版本信息 版本信息 可在此查看到每个版本的详细信息 1 2 下载文件 下载并将二进制文件 root localhost opt wget https github com porta

  • c语言 code space memory overlap,编程时Keil中常见的错误

    If px pc c warning 259 ERROR 260 pointer truncation 指针转换时部分偏移量被截断 此时指针常量 如char xdata 转为一个具有较小偏移区的 指针 如char idata ERROR 2

  • uniapp的两个跳转方式

    uniapp内置多种跳转方式 我这里介绍两个最常用的跳转 uni navigateTo和uni switchTab 前者为跳转到非TabBar页面 后者为跳转到TabBar页面 所谓TabBar就是底部导航栏配置的页面 例如下方的index

  • STM32HAL库-移植Unity针对微控制器编写测试框架

    概述 本篇文章介绍如何使用STM32HAL库 移植Unity 是一个为C语言构建的单元测试框架 侧重于使用嵌入式工具链 GitHub https github com ThrowTheSwitch Unity 硬件 STM32F103CBT

  • 【Hello Algorithm】堆和堆排序

    本篇博客简介 讲解堆和堆排序相关算法 堆和堆排序 堆 堆的概念 堆的性质 堆的表示形式 堆的增加 删除堆的最大值 堆排序 堆排序思路 时间复杂度为N的建堆方法 已知一个近乎有序的数组 使用最佳排序方法排序 堆 堆的概念 这里注意 这里说的堆

热门标签