当前位置: 首页 > news >正文

堆排序(含证明)

引言

前面我们讲过堆的基本操作的实现,现在给定一个int类型的数组,里面存放的数据是无序的,我们如何利用堆的思想来实现数组内数据的升序排列或降序排列呢?

通过前面讲到的堆的实现,我们可以想到,我们再开辟一块空间来模拟堆,将给定数组里的数据一一插入堆中(pushHeap)。这样做可以是可以,但如果是代码量未免有点大,而且还要额外开辟空间。如果是在平时考试时碰到这种题,那实现起来会有点麻烦。

如果能在给定数组上直接调整并减少点代码量就好了,今天我们就来讲讲如何这样实现堆排序。

堆排序主要涉及到两个步骤:1.建堆 2.利用堆的思想排序(具体怎么排序后面会讲)

接下来我们以排升序为例进行讲解。

如何建堆?

以建大堆为例:

如果是在原数组的基础上进行建大堆,通过前面的堆的学习和实现,我们可以通过在原数组进行向上调整法或向下调整法达到目的。

向上调整法建堆

我们以这个数组为例:

int a[7]={30,60,56,80,70,10,15};

db16d8a0dc2a4f67bd271283f8df41c4.png

要将它建成大堆:

514a5e2b44404f2bbccc36f313196c0e.png

从下向上遍历:从数组的第二个元素(下标为1)开始,依次向上遍历到第一个元素(下标为0)。这是因为堆的第一个元素(根节点)在构建过程中不需要进行向上调整。

向上调整:对于遍历到的每个元素(假设当前元素的下标为i),执行以下步骤:

  • 计算当前元素的父节点下标(parent = (i - 1) / 2)。
  • 比较当前元素与其父节点的值。
  • 如果当前元素的值大于其父节点的值,则交换这两个元素的位置。
  • 交换后,将当前元素的下标更新为其父节点的下标,并重复上述比较和交换步骤,直到当前元素的值不大于其父节点的值,或者当前元素成为根节点。
  • 完成建堆:当遍历完所有元素并完成所有必要的向上调整后,整个数组就形成了一个大顶堆。

附上代码:

void swap(dataType* x, dataType* y)
{dataType tmp = *x;*x = *y;*y = tmp;
}void adjustUp(dataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[child] > a[parent]) {swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void heapSort(int* a, int n) {for (int i = 1; i < n; i++) {adjustUp(a, i);}
}

向下调整法建堆

还是以原来的数组为例:

int a[7]={30,60,56,80,70,10,15};

将它建成大堆:

70f74c4107b6498fbc6520eee434163d.png

从最后一个非叶子节点开始,依次向上遍历每个节点(包括根节点)。对于每个节点,执行以下步骤:

  • 将当前节点视为父节点。
  • 比较其父节点与左右子节点的值(如果存在的话)。
  • 如果父节点的值小于左右子节点中的较小值,则交换父节点与较小子节点的值。
  • 将交换后的较小子节点视为新的父节点,重复上述比较和交换步骤,直到父节点的值大于或等于其所有子节点的值,或者父节点成为叶子节点。

当所有节点都按照上述步骤调整完毕后,整个数组就形成了一个大顶堆。

这里有一个问题,如何算最后一个出非叶子节点的下标呢?

在一个堆中,最后一个叶子节点的下标是n-1,那它父节点的下标就是(n-1-1)/2也就是(n-2)/2。

附上代码:

void swap(dataType* x, dataType* y)
{dataType tmp = *x;*x = *y;*y = tmp;
}
int getMax(dataType* a, int x, int y)
{if (a[x] > a[y]){return x;}else {return y;}
}
void adjustDown(dataType* a, int parent, int size)
{assert(a);while (parent < size){int lChild = 2 * parent + 1, rChild = 2 * parent + 2, swapChild;if (rChild < size) {swapChild = getMax(a, lChild, rChild);}else {swapChild = lChild;}if (swapChild < size && a[parent] < a[swapChild]) {swap(&a[parent], &a[swapChild]);parent = swapChild;}else {break;}}
}
void heapSort(int* a, int n) {//向下调整法for (int i = (n - 2)/2; i >= 0; i--) {adjustDown(a, i, n);}}

时间复杂度

向上调整法建堆

93e52c43bd69448a9efdfc7292ec5f93.jpg

 向下调整法建堆

8930ba646803479f84f7ff66f4d89109.png

总结

对比之下,向下调整法建堆的时间复杂度更低,所以我们更推荐用向下调整法建堆。

一个误区:排升序就是直接将原来无序的数组构建成小堆就可以了

说到建堆,无非就两种:要么建大顶堆,要么建小顶堆。但如果是排升序,很多人可能第一反应是直接建小顶堆就可以了。但是这样真的合适吗?我们以这个数组为例:

int a[5]={30,60,56,70,10};

e58f378a7f574d8cb603c35c7e37db64.png

 把它建成小顶堆会是这样:

099b6ba6382542d48dc376105ea8e18c.png

 对应的数组就是这样了:int a[5]={10,30,56,70,60};

我们发现这样调整后,数组里面的数据并不是完全按照升序排列的。为什么会这样呢?

我们需要知道,在小堆中,堆顶元素确实是最小的。但是,这并不意味着从堆顶到堆尾的所有元素都按升序排列。小堆的结构只保证了从根节点到每个叶子节点的路径上,元素是递增的。然而,不同路径上的元素之间并没有这样的保证。

所以,直接将原来无序的数组构建成小堆是不可行的办法。

排升序建大堆,排降序建小堆

那我们该怎么办呢?

答案是:排升序建大堆,排降序建小堆。

竟然跟我们最初的想法背道而驰,接下来我会讲解一下为什么要这么做以及具体如何实现。

我们以这个数组为例:

int a[5]={4, 10, 3, 5, 1}

具体步骤

1.我们先把将它建成大堆:

int a[5]={10,5,3,4,10}; 

6c8ad0247139419c86865056b7ebad55.png

2.交换堆顶元素与末尾元素:将堆顶元素(当前最大值)与序列末尾元素交换位置。

b7b48cdc67d74159afbe58cb02013d45.png

这一步骤将最大值“沉”到底部,同时保证了剩余元素组成的子序列仍满足堆的性质。

cfac0d24537541be837e6ec964f63d1c.png

3.调整剩余元素:将交换后的剩余元素(除去已排序的堆顶元素)重新调整为一个堆。

由于堆顶元素已被移到末尾,此时需要对剩余元素重新执行向下调整操作,使得新的堆顶元素成为剩余元素中的最大值。

39b3eafe4baa4326a0016302bdb1dfdc.png

 4.重复交换与调整:重复步骤2和步骤3,每次都将当前堆顶元素(即剩余部分的最大值)与末尾元素交换,并对剩余元素重新调整为堆。

53b9bdede498458a8ffed136970aeab9.png

         ①                          ②                         ③

 

0a79bc3a06e344dc84ef06fb4e22c601.png   ④                           ⑤                        ⑥

随着每一次交换和调整,有序序列逐渐扩大,堆的大小逐渐减小。

5.终止条件:当堆的大小减小到1时,整个序列已经有序,堆排序过程结束。

0577ca2b744048fcaf7619f587293fac.png

代码

void swap(dataType* x, dataType* y)
{dataType tmp = *x;*x = *y;*y = tmp;
}
int getMax(dataType* a, int x, int y)
{if (a[x] > a[y]){return x;}else {return y;}
}
void adjustDown(dataType* a, int parent, int size)
{assert(a);while (parent < size){int lChild = 2 * parent + 1, rChild = 2 * parent + 2, swapChild;if (rChild < size) {swapChild = getMax(a, lChild, rChild);}else {swapChild = lChild;}if (swapChild < size && a[parent] < a[swapChild]) {swap(&a[parent], &a[swapChild]);parent = swapChild;}else {break;}}
}
void heapSort(int* a, int n) {//向下调整法for (int i = (n - 2)/2; i >= 0; i--) {adjustDown(a, i, n);}int cnt = n - 1;while (cnt) {swap(&a[0], &a[cnt]);adjustDown(a, 0, cnt);--cnt;}}

时间复杂度

前面我们知道,通过向下调整法构建初始堆的时间复杂度为O(n),因为需要对n个元素进行一次向下调整操作。

交换堆顶元素与末尾元素并重新调整堆的过程需要重复n-1次,每次调整的时间复杂度为O(log n)。

因此,总的时间复杂度为O(n log n)。

如果排升序建小堆

在堆排序中,如果目标是进行升序排序,通常我们会选择构建大顶堆,而不是小顶堆。这是因为大顶堆的堆顶元素是最大的,通过不断地将堆顶元素与末尾元素交换并调整堆,可以逐步将序列排序为升序。

然而,如果尝试使用小顶堆来进行升序排序,步骤和弊端如下:

具体步骤

1.建堆:给定一个无序数组int a[5]={4, 10, 3, 5, 1},通过向下调整法将其构建为小顶堆int a[5]={1, 3, 4,5,10};

        1
       /  \
     3    4
     / \
   5   10

 

2.交换与调整:将小顶堆的堆顶元素(当前最小值)与数组末尾元素交换位置。

堆顶元素(1)与数组末尾元素(10)交换:      

      10
      /  \
    3    4
    / \
  5    1
由于交换后的堆顶元素可能不再是最小值,因此需要对剩余元素重新调整为小顶堆。

对应的数组表示变为:[10, 3, 4, 5, 1],此时,1已经被放到了数组最后的位置,不再参与后续堆化。

但是注意了,剩余元素[10, 3, 4, 5]需要重新调整为小顶堆。但是,不能直接通过下沉操作将3放到堆顶,因为这里的adjustDown函数是从堆顶开始与较大的子节点交换,直到找到合适的位置。在这个情况下,堆顶是10,它是当前堆中的最大值,下沉操作会将它与孩子几点钟较大的那一个孩子节点交换,也就是4,并不能把3交换上去。

正确的重新堆化过程:实际上,我们需要从最后一个非叶子节点开始(在这个例子中是4),向上逐个节点进行堆化,确保每个子树都满足小顶堆的性质。
然后,我们再将根节点(10)与其子节点中较小的一个进行交换,直到整个堆满足小顶堆的性质。
这个过程比简单地下沉操作要复杂得多,因为它可能涉及到多次交换和比较。

 

3.重复步骤:重复步骤2,每次都将新的堆顶元素(当前最小值)与数组末尾元素交换,并重新调整剩余元素为小顶堆。

弊端(与大顶堆相比)

一、效率低下

  • 小顶堆:
  1. 每次交换到末尾的是当前最小值。
  2. 需要对整个堆进行重新调整以得到下一个最小值。
  3. 迭代过程中每次都需要进行调整,导致整体效率低下。
  • 大顶堆:
  1. 每次交换到末尾的是当前最大值。
  2. 剩余元素自然形成新的堆,只需对堆顶元素进行向下调整。
  3. 每次迭代的时间复杂度相对较低。

二、稳定性问题

  • 小顶堆升序排序时,每次交换最小值可能破坏相同元素的相对顺序,稳定性问题更突出。

三、逻辑复杂性

  • 小顶堆用于升序排序反直觉。
  • 升序排序目标为从小到大排列,大顶堆堆顶为当前最大值,更符合需求。
  • 小顶堆需每次交换后进行复杂调整操作。

 

ps:在第一次学习数据结构的时候,我并没有学过堆排序。这篇博客也是本人到目前为止写的最心累的一篇博客!其实如果掌握好了前面堆的实现的内容,堆排序理解和实现起来并不难。所以前面的内容一定要理解到位!

 

 

 

 

相关文章:

堆排序(含证明)

引言 前面我们讲过堆的基本操作的实现&#xff0c;现在给定一个int类型的数组&#xff0c;里面存放的数据是无序的&#xff0c;我们如何利用堆的思想来实现数组内数据的升序排列或降序排列呢&#xff1f; 通过前面讲到的堆的实现&#xff0c;我们可以想到&#xff0c;我们再开…...

蓝桥杯模拟题不知名题目

题目:p是一个质数&#xff0c;但p是n的约数。将p称为是n的质因数。求2024最大质因数。 #include<iostream> #include<algorithm> using namespace std; bool fun(int x) {for(int i 2 ; i * i < x ; i){if(x % i 0)return false;}return true; } int main() …...

C#中的工厂模式

在C#中&#xff0c;工厂模式&#xff08;Factory Pattern&#xff09; 是一种常见的设计模式&#xff0c;它属于创建型模式&#xff0c;主要用于定义一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。通过使用工厂模式&#xff0c;客户端代码不需要直接实例化具体…...

深度学习与持续学习:人工智能的未来与研究方向

文章目录 1. 持续学习与深度学习1.1 深度学习的局限1.2 持续学习的定义 2. 目标与心智2.1 奖励假说2.2 心智的构成 3. 对研究方法的建议3.1 日常写作记录3.2 中立对待流行趋势 1. 持续学习与深度学习 1.1 深度学习的局限 深度学习注重“瞬时学习”&#xff0c;如ChatGPT虽在语…...

OGRE 3D----4. OGRE和QML共享opengl上下文

在现代图形应用开发中,OGRE(Object-Oriented Graphics Rendering Engine)和QML(Qt Modeling Language)都是非常流行的工具。OGRE提供了强大的3D渲染能力,而QML则用于构建灵活的用户界面。在某些应用场景中,我们需要在同一个应用程序中同时使用OGRE和QML,并且共享OpenGL…...

【Umi】常用配置

具体见&#xff1a;alias 1. 基础配置 1)配置别名alias 2)配置sourcemap devtool 配置项 3)添加hash 4)图片转base64 inlineLimit 配置项 5)设置JS压缩方式 jsMinifier (webpack) 、jsMinifierOptions 配置项 6)设置umi插件 plugins 配置项 7)设置打包后资源导入的路…...

Windows加固脚本

echo off REM 清屏 cls title 安全策略设置批处理 color f0 echo **************************************** echo write by afei echo https://www.jianshu.com/u/ea4c85fbe8c7 echo **************************************** pause cls color 3f echo ********************…...

玩游戏常常出现vc++runtime library error R6025 这是什么意思,该怎么解决?

当玩游戏时常常出现“vc runtime library error R6025”错误&#xff0c;这通常表明微软C开发运行库组件存在问题。以下是对该错误及其解决方法的详细解释&#xff1a; 错误含义 “vc runtime library error R6025”是一个与Visual C运行时库相关的错误&#xff0c;该错误表明…...

AGX orin下电控制

AGX orin下电主要有两种&#xff0c;一种通过软件控制下电&#xff0c;另一种通过按键强制关机。下电流程和电脑关机流程类似。 AGX orin核心板与扩展板 AGX orin核心板由英伟达生产&#xff0c;不提供原理图&#xff0c;通过下图所示连接器与扩展板连接。 AGX orin扩展板&am…...

flutter 报错 error: unable to find git in your path.

项目issue&#xff1a;WIndows: "Unable to find git in your PATH." if terminal is not in admin mode Issue #123995 flutter/flutter 解决办法&#xff0c; 方法一&#xff1a;每次想要运行flutter的时候以管理员方式运行&#xff0c;比如以管理方式运行vsco…...

芯科科技率先支持Matter 1.4,推动智能家居迈向新高度

Matter 1.4引入核心增强功能、支持新设备类型&#xff0c;持续推进智能家居互联互通 近日&#xff0c;连接标准联盟&#xff08;Connectivity Standard Alliance&#xff0c;CSA&#xff09;发布了Matter 1.4标准版本。作为连接标准联盟的重要成员之一&#xff0c;以及Matter标…...

C语言数据相关知识:静态数据、越界与溢出

1、静态数组 在 C 语言中&#xff0c;数组一旦被定义后&#xff0c;占用的内存空间就是固定的&#xff0c;容量就是不可改变的&#xff0c;既不能在任何位置插入元素&#xff0c;也不能在任何位置删除元素&#xff0c;只能读取和修改元素&#xff0c;我们将这样的数组称为静态…...

文本分析之余弦相似度

余弦相似度(Cosine Similarity)是一种用于衡量两个非零向量之间相似度的指标,尤其常用于文本分析和自然语言处理领域。其核心思想是通过计算两个向量的夹角余弦值来评估它们的相似性。具体而言,余弦相似度的值范围从-1到1,其中1表示两个向量完全相同,0表示它们之间没有相…...

【VUE3】【Naive UI】<n-button> 标签

【VUE3】【Naive UI】&#xff1c;n-button&#xff1e; 标签 **type**- 定义按钮的类型&#xff0c;这会影响按钮的颜色和样式。**size**- 设置按钮的大小。**disabled**- 布尔值&#xff0c;控制按钮是否处于禁用状态。**loading**- 布尔值&#xff0c;表示按钮是否处于加载状…...

css使盒子在屏幕的地点固定

在 CSS 中&#xff0c;要将一个元素固定在页面的某个位置&#xff0c;可以使用 position: fixed 属性。以下是详细的代码示例和中文解释&#xff1a; <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta n…...

Transformers快速入门代码解析(六):注意力机制——Transformer Encoder:执行顺序解析

Transformer Encoder&#xff1a;执行顺序解析 引言执行顺序解析1. 设置模型检查点和分词器2. 输入预处理操作说明&#xff1a; 3. 加载模型配置configconfig 包含的主要参数常见配置&#xff08;BERT-base&#xff09; 4. 初始化 TransformerEncoder5. Transformer Encoder 的…...

图像小波去噪与总变分去噪详解与Python实现

目录 图像小波去噪与总变分去噪详解与实现1. 基础概念1.1 噪声类型及去噪问题定义1.2 小波去噪算法基础1.3 总变分去噪算法基础2. 小波去噪算法2.1 理论介绍2.2 Python实现及代码详解2.3 案例分析3. 总变分去噪算法3.1 理论介绍3.2 Python实现及代码详解3.3 案例分析4. 两种算法…...

【深度学习基础】预备知识 | 微积分

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PyTorch深度学习 ⌋ ⌋ ⌋ 深度学习 (DL, Deep Learning) 特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网络等算法模型基础上&#xff0c;结合当代大数据和大算力的发展而发展出来的。深度学习最重…...

CTF-PWN glibc源码阅读[1]: 寻找libc中堆结构的定义(2.31-0ubuntu9.16)

源代码在这里下载 来到malloc/malloc.c 在980行发现这段代码 // 定义最大 mmap 值为 -4 #define M_MMAP_MAX -4// 如果没有定义 DEFAULT_MMAP_MAX&#xff0c;则将其定义为 65536 #ifndef DEFAULT_MMAP_MAX #define DEFAULT_MMAP_MAX (65536) #endif// 引…...

宏集eXware物联网网关在水务管理系统上的应用

一、前言 水务管理系统涵盖了对城市水网、供水、排水、污水处理等多个环节的监控与管理。随着物联网&#xff08;IoT&#xff09;技术的快速发展&#xff0c;物联网网关逐渐成为水务管理系统中的关键组成部分。 宏集物联网网关以其高效的数据采集、传输和管理功能&#xff0c…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...