java堆排序原理与实现方法分析

本文实例讲述了java堆排序原理与实现方法。分享给大家供大家参考，具体如下：

堆是一个数组，被看成一个近似完全二叉树。

举例说明：

堆的性质：

1.已知元素在数组中的序号为i

其父节点的序号为 i/2的整数
其左孩子节点的序号为2*i
其右孩子节点的序号为2*i+1

2.堆分为最大堆和最小堆

在最大堆中，要保证父节点的值大于等于其孩子节点的值
在最小堆中，要保证父节点的值小于等于其孩子节点的值

java实现堆排序

public class MyHeapSort {
  public void Heap_Sort(int[] A) {
    /**
     * 这个函数完成堆排序
     * 先构建一个最大堆
     * 将数组中第一个元素和最后一个交换，
     * 堆的长度减一
     * 在从第一个位置开始保证堆的性质调用Max_heapify()函数。
     * 这样保证目前最大的元素在数组的最后位置。
     * 以此类推，直到最后一个元素。
     */
    Build_Max_Heap(A);
    for (int i = A.length - 1; i >= 1; i--) {
      int temp = A[0];
      A[0] = A[i];
      A[i] = temp;
      Max_heapify(A, 0, i);
    }
  }
  public void Build_Max_Heap(int[] A) {
    /**
     * 这个函数用来构建堆
     * A:待排序的数组
     * （for循环中i的值从数组长度的一般开始取，是因为完全二叉树的性质，
     * 一半的节点叶根节点所以从叶节点开始向上遍历来保证堆的性质）
     */
    for (int i = A.length/2; i >= 0; i--) {
      Max_heapify(A, i, A.length);
    }
  }
  public void Max_heapify(int[] A, int i, int heap_size) {
    /**这个函数用来维护堆的性质，
     * 保证以序号为i的元素为根节点的子树中，父节点的值大于其孩子节点的值。
     * A:待排序数组
     * i：在数组A中的序号
     * heap_size:堆的大小
     */
    int largest = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;
    if (l < heap_size && A[l] > A[i]) largest = l;
    if (r < heap_size && A[r] > A[largest]) largest = r;
    if (largest != i) {
      int temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
      Max_heapify(A, largest, heap_size);
    }
  }
  public static void main(String[] args) throws Exception {
    System.out.println("我们测试结果：");
    int[] a = new int[]{1,3,2,5,34,23,44,15,67,45};
    new MyHeapSort().Heap_Sort(a);
    for (int x : a) System.out.println(x);
  }
}

代码中例子的运行结果：

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

赞 (0)

相关推荐

  • Java排序算法之堆排思想及代码实现

    Java排序算法之堆排思想及代码实现

    在介绍堆排序前,我们需要了解一下一种数据结构 -- 顶堆. 什么是顶堆? 它是一颗完全二叉树,顶堆有大顶堆和小顶堆两种.所谓大顶堆就是在这颗完全二叉树中,任何一颗子树都满足:父结点的值 > 孩子结点的值:小顶堆则相反. 如图: 什么是堆排序(Heapsort)? 利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种.可以利用数组的特点快速定位指定索引的元素. 现在给我们一个无序数组,我们将其从小到大排序,使用堆排序的实现步骤和思想如下: 1.让这个数组变成一个大根堆 2.将最后一

  • Java内存溢出和内存泄露

    虽然jvm可以通过GC自动回收无用的内存,但是代码不好的话仍然存在内存溢出的风险. 一.为什么要了解内存泄露和内存溢出? 1.内存泄露一般是代码设计存在缺陷导致的,通过了解内存泄露的场景,可以避免不必要的内存溢出和提高自己的代码编写水平: 2.通过了解内存溢出的几种常见情况,可以在出现内存溢出的时候快速的定位问题的位置,缩短解决故障的时间.  二.基本概念  理解这两个概念非常重要. 内存泄露:指程序中动态分配内存给一些临时对象,但是对象不会被GC所回收,它始终占用内存.即被分配的对象可达但已无

  • Java 堆内存溢出原因分析

    Java 堆内存溢出原因分析

    前言 任何使用过基于 Java 的企业级后端应用的软件开发者都会遇到过这种低劣.奇怪的报错,这些报错来自于用户或是测试工程师: java.lang.OutOfMemoryError:Java heap space. 为了弄清楚问题,我们必须返回到算法复杂性的计算机科学基础,尤其是"空间"复杂性.如果我们回忆,每一个应用都有一个最坏情况特征.具体来说,在存储维度方面,超过推荐的存储将会被分配到应用程序上,这是不可预测但尖锐的问题.这导致了堆内存的过度使用,因此出现了"内存不够&

  • Java内存区域与内存溢出异常详解

    Java内存区域与内存溢出异常详解

    Java内存区域与内存溢出异常 概述 对于 C 和 C++程序开发的开发人员来说,在内存管理领域,程序员对内存拥有绝对的使用权,但是也要主要到正确的使用和清理内存,这就要求程序员有较高的水平. 而对于 Java 程序员来说,在虚拟机的自动内存管理机制的帮助下,不再需要为每一个 new 操作去写配对的 delete/free 代码,而且不容易出现内存泄漏和内存溢出问题,看起来由虚拟机管理内存一切都很美好.不过,也正是因为 Java 程序员把内存控制的权力交给了 Java 虚拟机,一旦出现内存泄漏和

  • Java常见内存溢出异常分析与解决

    Java虚拟机规范规定JVM的内存分为了好几块,比如堆,栈,程序计数器,方法区等,而Hotspot jvm的实现中,将堆内存分为了三部分,新生代,老年代,持久带,其中持久带实现了规范中规定的方法区,而内存模型中不同的部分都会出现相应的OutOfMemoryError错误,接下来我们就分开来讨论一下.java.lang.OutOfMemoryError这个错误我相信大部分开发人员都有遇到过,产生该错误的原因大都出于以下原因: JVM内存过小.程序不严密,产生了过多的垃圾. 导致OutOfMemor

  • Java堆内存又溢出了！教你一招必杀技(推荐)

    Java堆内存又溢出了！教你一招必杀技(推荐)

    JAVA堆内存管理是影响性能主要因素之一. 堆内存溢出是JAVA项目非常常见的故障,在解决该问题之前,必须先了解下JAVA堆内存是怎么工作的. 先看下JAVA堆内存是如何划分的,如图: 1.JVM内存划分为堆内存和非堆内存,堆内存分为年轻代(Young Generation).老年代(Old Generation),非堆内存就一个永久代(Permanent Generation). 2.年轻代又分为Eden和Survivor区.Survivor区由FromSpace和ToSpace组成.Eden

  • 完美解决java读取大文件内存溢出的问题

    1. 传统方式:在内存中读取文件内容 读取文件行的标准方式是在内存中读取,Guava 和Apache Commons IO都提供了如下所示快速读取文件行的方法: Files.readLines(new File(path), Charsets.UTF_8); FileUtils.readLines(new File(path)); 实际上是使用BufferedReader或者其子类LineNumberReader来读取的. 传统方式的问题: 是文件的所有行都被存放在内存中,当文件足够大时很快就会

  • Java编程常见内存溢出异常与代码示例

    Java 堆是用来存储对象实例的, 因此如果我们不断地创建对象, 并且保证 GC Root 和创建的对象之间有可达路径以免对象被垃圾回收, 那么当创建的对象过多时, 会导致 heap 内存不足, 进而引发 OutOfMemoryError 异常. /** * @author xiongyongshun * VM Args: java -Xms10m -Xmx10m -XX:+HeapDumpOnOutOfMemoryError */ public class OutOfMemoryErrorTe

  • 浅谈java内存管理与内存溢出异常

    浅谈java内存管理与内存溢出异常

    说到内存管理,笔者这里想先比较一下java与C.C++之间的区别: 在C.C++中,内存管理是由程序员负责的,也就是说程序员既要完成繁重的代码编写工作又要时常考虑到系统内存的维护 在java中,程序员无需考虑内存的控制和维护,而是交由JVM自动管理,这样就不容易出现内存泄漏和溢出的问题.然而,一旦出现内存泄漏和溢出方面的问题,如果不了解JVM的内存管理机制就很难找到错误所在. 1.JVM运行时数据区 JVM在运行java程序的时候会将它所管理的内存划分为若干个不同的区域,这些区域不仅有自己的用途

  • java堆排序原理与实现方法分析

    java堆排序原理与实现方法分析

    本文实例讲述了java堆排序原理与实现方法.分享给大家供大家参考,具体如下: 堆是一个数组,被看成一个近似完全二叉树. 举例说明: 堆的性质: 1.已知元素在数组中的序号为i 其父节点的序号为 i/2的整数 其左孩子节点的序号为2*i 其右孩子节点的序号为2*i+1 2.堆分为最大堆和最小堆 在最大堆中,要保证父节点的值大于等于其孩子节点的值 在最小堆中,要保证父节点的值小于等于其孩子节点的值 java实现堆排序 public class MyHeapSort { public void Hea

  • Python堆排序原理与实现方法详解

    Python堆排序原理与实现方法详解

    本文实例讲述了Python堆排序原理与实现方法.分享给大家供大家参考,具体如下: 在这里要事先说明一下我也是新手,很多东西我了解不是很深入,写算法完全是锻炼自己逻辑能力同时顺带帮助读研的朋友么解决一些实际问题.所以很多时候考虑的东西不是很全面能请各位看到博文的大牛们指正.对于排序算法说实在的我觉得已经写烂了,但是为什么还是要过一遍呢?还是为了能够打牢基础.说一下自己的看法,对于已经的玩烂的算法因该怎么学.首先最重要的还是了解算法的基本模型和算法思想,我觉得这是非常重要的.其次的话首先先尝试自己实

  • 汉明码编码原理及校验方法分析

    汉明码编码原理及校验方法分析

    目录 1.奇偶校验 2.汉明码 汉明码怎么分组: 校验码的位置: 从发送者的角度,我该怎么发用上汉明码的数据呢: 我是接收者,我收到了一串汉明码,怎样用汉明码的性质来检错呢: 1.奇偶校验 我们约定一串编码里1的个数是偶数个,那么这串编码里携带的信息就是对的,否则就是错的.我们可以在开头对这串编码加一位校验码实现奇偶校验. 例子: 我们想传输10010这串码,那么在传输的时候,就传010010,其中在开头的0就是校验位. 我们想传输10000这串码,那么在传输的时候,就传110000,其中在开头

  • Java中对象的销毁方法分析

    本文较为详细的分析了Java中对象的销毁方法.分享给大家供大家参考.具体分析如下: Java中的基本数据类型变量和对象的名称引用变量如定义在方法中,都为局部变量.但对象本身不一定是局部生命周期.如函数外存在其他对该对象的引用变量,则该对象的生命周期延伸至该其他引用变量所在的块. 如从被调用函数参数引用传值或返回值到主调用函数所在的对象类型变量中,则该对象都仍存在(但被调用函数的该对象的引用变量生命周期结束,因此引用变量是局部变量),此时对象突破了局部变量的局部生命期. Java对象销毁 Java

  • Android4.4开发之电池低电量告警提示原理与实现方法分析

    本文实例讲述了Android4.4电池低电量告警提示原理与实现方法.分享给大家供大家参考,具体如下: 之前版本的电池电量低是通过发送 intent ACTION_BATTERY_LOW来实现的,而在android4.4中,通过发送intent ACTION_BATTERY_CHANGED,也就是电池电量只要变化就检查是否需要低电量告警,并且实现挪到了PowerUI中. 路径: frameworks/base/packages/SystemUI/src/com/android/systemui/p

  • Java 继承原理与用法实例分析

    本文实例讲述了Java 继承原理与用法.分享给大家供大家参考,具体如下: 继承的概念 继承是java面向对象编程技术的一块基石,因为它允许创建分等级层次的类. 继承就是子类继承父类的特征和行为,使得子类对象(实例)具有父类的实例域和方法,或子类从父类继承方法,使得子类具有父类相同的行为. 类的继承格式 在 Java 中通过 extends 关键字可以申明一个类是从另外一个类继承而来的,一般形式如下: class 父类 { } class 子类 extends 父类 { } 为什么需要继承 接下来

  • PHP防止sql注入小技巧之sql预处理原理与实现方法分析

    本文实例讲述了PHP防止sql注入小技巧之sql预处理原理与实现方法.分享给大家供大家参考,具体如下: 我们可以把sql预处理看作是想要运行的 SQL 的一种编译过的模板,它可以使用变量参数进行定制. 我们来看下它有什么好处: 预处理语句大大减少了分析时间,只做了一次查询(虽然语句多次执行). 绑定参数减少了服务器带宽,你只需要发送查询的参数,而不是整个语句. 预处理语句针对SQL注入是非常有用的,因为参数值发送后使用不同的协议,保证了数据的合法性. 这种预处理呢,可以通过两个方式,咱们这次要说

  • JavaScript设计模式之门面模式原理与实现方法分析

    本文实例讲述了JavaScript设计模式之门面模式原理与实现方法.分享给大家供大家参考,具体如下: 外部与一个子系统的通信必须通过一个系统的一个门面对象进行,这就是门面模式. 门面模式具备如下两个角色: 1. 门面角色 客户端可以调用这个角色方法,此角色中有子系统的应用(知晓相关的(一个或多个)子系统的功能和责任).本角色会将所有从客户端发来的请求委派到相应的子系统去. 2. 子系统角色 可以同时有一个或多个子系统.每一个子系统都不是一个单独的类,而是一些类的集合.每一个子系统都可以被客户端直

  • 《javascript设计模式》学习笔记三：Javascript面向对象程序设计单例模式原理与实现方法分析

    本文实例讲述了Javascript面向对象程序设计单例模式原理与实现方法.分享给大家供大家参考,具体如下: 1.单例模式概述 源自百度百科对于单例模式的定义: 单例模式的意思就是只有一个实例.单例模式确保某一个类只有一个实例,而且自行实例化并向整个系统提供这个实例.这个类称为单例类. 在javascript的世界里,其实没有严格的对象和类定义,"一切皆对象"使得javascript中都是对象,不能像java,c++或者php使用特定的方法返回一个实例来实现,因此对javascript来

  • Java包装类原理与用法实例分析

    本文实例讲述了Java包装类原理与用法.分享给大家供大家参考,具体如下: 产生: 为了提高数据类型的的面向对象性,所以产生了包装类,包装类中有各种便利的方法 数据类型对应的包装类 使用: 包装类可以实现将基本类型转换成字符串(或者字符串转换成基本类型): 1.包装类中方法parseXXX 2.构造器 3.对于String,使用String中的valueof能将基本数据类型转换成字符串 包装类的实例可以与基本数据类型比较: 直接把实例中包装的数值拿出来比较 当如果是包装类实例的比较的话,比较的是所

随机推荐