算法之堆排序

       堆排序是一种基于比较的排序算法,通过构建二叉堆(Binary Heap),可以利用堆的性质进行高效的排序。二叉堆是一个完全二叉树,可以有最大堆和最小堆两种形式。在最大堆中,父节点的值总是大于或等于其子节点的值;在最小堆中,父节点的值总是小于或等于其子节点的值。

先了解原理 

       在最大堆中,每次操作都会选出当前堆中的最大元素。这个元素被放置到堆的顶部,然后与数组的最后一个元素交换位置。交换后,该元素从堆中移除,因为它已经被放置在其最终位置。接下来,我们重新调整剩余的堆结构,以确保堆的最大元素位于顶部,为下一次操作做准备。通过不断重复这个过程,我们能够逐步构建出一个有序的数组。同理,小堆也是一样的

当然实际编程的时候要考虑式子

R[V]>=R[2V]  , R[V]>=R[2V+1]

咱们话不多说直接看题吧。

看题的时候先思考参数,v代表什么,n代表什么?v是根节点编号,n是堆的元素数。

i=v,都是根节点编号,R[0]=R[i],就是将根节点存到R[0]。根据式子R[V]>=R[2V]  , R[V]>=R[2V+1]

所以可以知道j=2*i   是出于什么目的了吧。

然后就是if判断j<=n应该很容易理解吧,因为n是总的堆的数目,j肯定要小于或者等于n的

至于那个if(j<n&&R[j]<R[j+1])  j++

这个很好理解,就是简单的将下面节点最大的用j表示,怎么说呢,就是你想想一颗二叉树,左节点是3,而右节点是4,而大堆肯定是选大的和根节点比较。所以才有这个if判断,如果右节点大,就让这个j++,让它指向右节点

然后就是那个空,明显是R[j] >=R[0]   ,因为前面已经将R[0]=R[i],所以这里和R[0]进行比较就行了。

然后第二个空,肯定是构建大堆呗,Heapify(R,i,n),第三个空 i>1或i>=2,第四个空是R[1]=R[0]。

相关推荐

  1. 排序算法排序

    2024-05-26 00:56:18       65 阅读
  2. C#算法排序算法

    2024-05-26 00:56:18       29 阅读
  3. 前端算法 -- 计数排序

    2024-05-26 00:56:18       56 阅读
  4. 排序算法-排序

    2024-05-26 00:56:18       37 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-05-26 00:56:18       91 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-05-26 00:56:18       97 阅读
  3. 在Django里面运行非项目文件

    2024-05-26 00:56:18       78 阅读
  4. Python语言-面向对象

    2024-05-26 00:56:18       88 阅读

热门阅读

  1. 从零学算法1542

    2024-05-26 00:56:18       33 阅读
  2. 在Juniper SRX系列防火墙上配置DNS

    2024-05-26 00:56:18       33 阅读
  3. k8s配置pods滚动发布

    2024-05-26 00:56:18       40 阅读
  4. Git下载慢

    2024-05-26 00:56:18       32 阅读
  5. 使用FFmpeg进行多媒体处理的完整指南

    2024-05-26 00:56:18       39 阅读
  6. MySQL技术点合集

    2024-05-26 00:56:18       33 阅读
  7. PaddleClas 指定gpu

    2024-05-26 00:56:18       32 阅读
  8. PHP开发安全:专家级代码审计策略与方法

    2024-05-26 00:56:18       33 阅读
  9. Flutter 中的 ExpandIcon 小部件:全面指南

    2024-05-26 00:56:18       32 阅读
  10. Python项目开发实战:五子棋游戏(案例教程)

    2024-05-26 00:56:18       31 阅读
  11. QGraphicsView中鼠标位置图像缩放时不变

    2024-05-26 00:56:18       32 阅读
  12. 【Spark】加大hive表在HDFS存的每个文件的大小

    2024-05-26 00:56:18       30 阅读
  13. Python案例题目,入门小白题

    2024-05-26 00:56:18       36 阅读
  14. HTML5 Canvas图形绘制技术应用

    2024-05-26 00:56:18       27 阅读