堆排序(排升序为啥建大堆,排降序为啥建小堆)

article/2025/7/22 6:08:24

简介:

  之前对堆排序认识的不是很透彻,今天回过头来再把堆排序的知识整理整理!以及排升序为什么要建大堆,排降序要建小堆。

正文:

  首先我们要知道:
  ①堆的逻辑是一颗完全二叉树;
  ②它使用的是顺序存储(也就是数组);
  ③它的作用:一般都是用于找最值。

排序也就是对数组的元素按照大小规则进行摆放。

堆排序的过程:
1、建堆
2、对建好的堆进行向下调整。

可能有人会疑问?堆已经建立好了,为什么还要向下调整?
来看看下面的解释:
我们先给定一个数组arr[ ] = { 7, 6, 3, 5, 4, 1, 2 }; 将其排成一个大堆。如下图:
在这里插入图片描述
  当我们建好堆之后,我们发现这个堆层序遍历下来是一个降序的。那么要将它变成一个升序的顺序,就要将它逆序。
  也就是交换堆顶和最后一个元素的位置,然后从堆顶开始向下调整,每交换一个位置,就多一个数据已经排好升序。
  可能看到这还很迷糊。没关系,继续看下面的图。

在这里插入图片描述
我们可以看到,排升序的话,使用大堆是非常方便的,我们每次向下调整都可以得到剩余数据的最大值,即堆顶元素。然后放到最后,使用分治的思想,每调整一次,要排序的数据就少一个。当交换到最后一个结点时,数组已经排好序了。
因为是从堆顶选择第一个元素与最后一个元素交换,所以堆排序实质上还是选择排序。

那么有人会疑惑为什么不使用小堆排升序呢?
我们再想想:首先使用堆排序主要是用堆顶元素,如果使用小堆排升序,此时堆顶的元素是最小的,当我们取出堆顶元素时,此时小根堆的性质就变了,那么下次就找不到第二小的元素了,还要重新建堆。所以不能使用小堆排升序。有兴趣的可以自己来画图走一走。


堆排序的代码如下:

void Swap(int *a, int *b)
{int tmp = *a;*a = *b;*b = tmp;
}
//建大堆
void AdjustDown(int arr[], int size, int root){int left = 2 * root + 1;int right = 2 * root + 2;int max;//没有左孩子if (left >= size){return;}//右孩子存在且大于左孩子if (right < size && arr[right] > arr[left]){max = right;}else{max = left;}if (arr[root] >= arr[max]){return;}Swap(arr + root, arr + max);AdjustDown(arr, size, max);
}
void CreateHeap(int arr[], int size){for (int i = (size - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, size, i);}
}
void HeapSort(int arr[], int size){CreateHeap(arr, size);for (int i = 0; i < size; i++){Swap(arr, arr + size - i - 1);AdjustDown(arr, size - i - 1, 0);}
}

http://chatgpt.dhexx.cn/article/pGJydcgw.shtml

相关文章

残差网络Residual Networks-残差网络的创建、训练、测试、调参

残差网络的创建、训练、测试、调参加粗样式 在Keras中实现残差网络模型的创建&#xff0c;并通过模型来实现对图片的分类。 残差网络的预备知识 网络越深越好&#xff1f; 随着网络层级的不断增加&#xff0c;模型精度不断得到提升&#xff0c;而当网络层级增加到一定的数目…

堆排序,为什么升序排列要建大堆,降序排列要建小堆

堆排序中用到了建立大小堆和向下调整的内容&#xff0c;对这些内容有些不了解的同学可以去补一补专门写堆的博客&#xff0c;方便更好的理解堆排序数据结构之堆&#xff08;Heap&#xff09;&#xff0c;堆的相关操作&#xff0c;用堆模拟优先级队列。 如果把待排序序列分为未排…

操作系统——动态分配算法(首次适应算法,最佳适应算法,最坏适应算法及回收)

操作系统——动态分配 写的时间早了&#xff0c;有些许漏洞和不足&#xff0c;请大家不要介意 分配方式可分为四类:单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法四种方式&#xff0c;其中动态分区分配算法就是此实验的实验对象。动态分区分配又称为…

pandas中对列进行排序(单列/多列)/(升序/降序)/(多列升序,降序控制)

前言 我想把数据分析刻进DNA里 如下面的数据,对price,要进行最简单的升序操作: 这个好整: import pandas as pdshop pd.read_csv("data/shop.csv", index_colid)shop.sort_values(byprice, inplaceTrue)结果: 如果你想整活(被迫)要把数据进行降序排列: 按照降序,传…

最先适应法、最佳适应法、下次适配法、最差适配法

题&#xff1a; 分析&#xff1a; 1. 首先分析是不是最差适配法&#xff0c;最差适配法意思是首先找到最大的内存空间进行分配&#xff0c; 对于请求的5K存储空间&#xff0c;首先找到地址200K容量为56K的地方进行分配&#xff0c;然后剩余51K。 再对请求的15K进行分配&…

自适应滤波器更新算法-EP1

自适应滤波器更新算法-EP1 自适应滤波器是回声消除系统中非常重要的一个功能模块&#xff0c;而对于自适应滤波器来说&#xff0c;如果更新滤波器系数则是关键所在。本文将介绍几种现有的滤波器更新算法&#xff0c;并附上Matlab测试代码。 1、LMS算法 1.1算法原理 LMS算法即…

自适应神经网络算法原理,单神经元自适应控制

关于神经网络自适应控制求助 这句话你可以直接用&#xff0c;不用加引用。因为这句话是很容易验证的。在网络层数、隐含层节点数逐渐增加&#xff0c;训练次数增加之后&#xff0c;他的拟合能力也是不断增加的&#xff0c;所以说&#xff0c;他可以以任意精度逼近任何非线性连…

【转载】梯度下降算法的参数更新公式

NN这块的公式&#xff0c;前馈网络是矩阵乘法。损失函数的定义也是一定的。 但是如何更新参数看了不少描述&#xff0c;下面的叙述比较易懂的&#xff1a; 1、在吴恩达的CS229的讲义的第四页直接给出参数迭代公式 在UFLDL中反向传导算法一节也是直接给出的公式 2、例子&#x…

Java中Comparator的个人简单理解(升序降序)与使用

目录 Java自定义排序返回值简单记忆理解实践LInkedList升序&#xff08;默认情况&#xff09;降序 PriorityQueue升序下的小顶堆&#xff08;默认情况&#xff09;降序下的大顶堆 总结补充数组类型自定义排序降序排序 数组 Java自定义排序返回值简单记忆理解 默认情况下&#…

深度残差收缩网络(从信号降噪的角度进行理解)

本文探讨了深度残差收缩网络的另一种理解方式。 传统信号降噪算法的常见步骤是&#xff1a; ① 采用某种信号变换方法&#xff08;例如小波、经验模态分解&#xff09;&#xff0c;将含噪信号变换到另外一种形态&#xff08;例如小波系数、本征模态分量等&#xff09;。在这些…

NIPS 2016 深度学习 迁移学习 ---残差转移网络用于无监督领域自适应

深度学习的成功得益于大量的标注数据&#xff0c;而数据标注是非常消耗资源的。当一个问题中缺少标注数据时&#xff0c;可以从另一个源中所学知识迁移过来&#xff0c;并且用于新问题中。 清华大学的学者提出了一种新的方法&#xff08;https://arxiv.org/pdf/1602.04433.pdf&…

深度残差网络+自适应参数化ReLU激活函数(调参记录21)Cifar10~95.12%

本文在调参记录20的基础上,将残差模块的个数,从27个增加到60个,继续测试深度残差网络ResNet+自适应参数化ReLU激活函数在Cifar10数据集上的表现。 自适应参数化ReLU函数被放在了残差模块的第二个卷积层之后,这与Squeeze-and-Excitation Networks或者深度残差收缩网络是相似…

已知两个长度分别为m 和 n 的升序链表,合并降序链表,求时间复杂度

王道数据结构上一道题&#xff1a; 之前我看到一个电子版的书&#xff0c;上边答案解析写的有点错误&#xff0c; 听说有些同学买的实体书上&#xff0c;答案解析也是这样写的 这个是刊印错误&#xff0c;很显然2Max( m , n )大于等于 m n 而且这个解析也不够清晰。 解析&a…

波束形成 常见自适应波束形成算法信(干)噪比增益影响因素

0、其他补充 均匀线阵波束形成器的信噪比增益上确界可由下式表示&#xff1a; 其中为阵元数&#xff0c;所以为了方便起见&#xff0c;一般的稳健自适应波束形成算法在仿真过程中的阵元数量均设置为10。 阵列的导向矢量可由下式表示&#xff1a; 以首个阵元为参考阵元&#xff…

两个升序链表合并成一个降序链表的时间复杂度

王道考研P7 第六题 【2013年统考真题】已知两个长度分别为m和n的升序链表&#xff0c;若将它们合并为长度为mn的一个降序链表&#xff0c;则最坏情况下的时间复杂度是&#xff08;&#xff09; A. O(n) B. O(mn) C. O(min(m,n)) D. O(max(m,n)) 答案是D 注意&#xff0c;此题…

无线传感器网络路由优化中的能量均衡LEACH改进算法

文章目录 一、理论基础1、LEACH算法概述2、改进的LEACH算法 二、算法流程图三、仿真实验与分析四、参考文献 一、理论基础 1、LEACH算法概述 请参考这里。 2、改进的LEACH算法 改进的LEACH算法&#xff08;LEACH-N&#xff09;主要针对LEACH算法分簇阶段的缺陷而改进的&…

机器学习之自适应增强(Adaboost)

1.Adaboost简介 **Adaptive boosting(自适应增强)是一种迭代算法&#xff0c;其核心思想是针对同一个训练集训练不同的弱分类器&#xff0c;然后把这些弱分类器集合起来&#xff0c;构成一个强分类器&#xff0c;Adaboost可处理分类和回归问题。了解Adaboost算法之前&#xff…

自适应阈值(adaptiveThreshold)分割原理及实现

背景介绍及原理 前面介绍了OTSU算法和最大熵算法&#xff0c;但这两种算法都属于全局阈值法&#xff0c;所以对于某些光照不均的图像&#xff0c;这种全局阈值分割的方法会显得苍白无力&#xff0c;如下图&#xff1a; 显然&#xff0c;这样的阈值处理结果不是我们想要的&…

优化算法+神经网络:神经网络自动参数优化

当智能群优化算法遇上神经网络 优化算法进行神经网络的参数寻优&#xff0c;解放深度调参1.已经实现的Genetic Algorithm优化Neural Network2.已经实现的PSO优化Neural Network3.已实现的SSA[^1]优化Neural Network 三种方法的可视化搜索过程对比三种优化算法性能总结总结目前来…

Java stream().sorted()实现排序(升序、降序、多字段排序)

1 自然排序 sorted()&#xff1a;自然排序&#xff0c;流中元素需实现Comparable接口 package com.entity;import lombok.*;Data ToString AllArgsConstructor NoArgsConstructor public class Student implements Comparable<Student> {private int id;private String …