当前位置:  编程技术>java/j2ee

JAVA算法起步之堆排序实例

    来源: 互联网  发布时间:2014-11-01

    本文导语:  学习堆排序,首先需要明白堆的概念,堆是一个数组。可以近似当做完全二叉树的数组存储方式。但是跟他还有其他的性质,就是类似于二叉排序树。有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小...

学习堆排序,首先需要明白堆的概念,堆是一个数组。可以近似当做完全二叉树的数组存储方式。但是跟他还有其他的性质,就是类似于二叉排序树。有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小堆的是根节点的值小于其子节点的值。堆排序一般用的是最大堆,而最小堆可以构造优先队列。堆里面有一个方法是用来维护堆的性质,也就是我们下面代码中的maxheap方法,这是维护最大堆性质的方法,第一个参数就是堆也就是数组,第二个参数是调整堆的具体节点位置,可能这个节点的值不符合最大堆的性质,那么这个值得位置就作为参数,而size其实是堆内实际存储的有效元素个数。可能数组的长度就是堆内实际存储的元素个数,但是不一定所有的数据我们都需要进行构建最大堆。算法导论中说的得到左子结点是2xi但是我们数组是从0开始计数的,所以左子结点就成了2xi+1,buildheap就是构建一个最大堆,我们去2分之长度的原因是,这些点的子节点都是叶子节点,所以我们通过从下向上进行排序来构建一个最大堆。保证了我们堆内所有节点都满足最大堆性质。最后堆排序就是把第一个节点取出来,将剩下的节点再进行堆排序,再取出根节点。这样保证我们每次取出都是最大值。

代码如下:

public class HeapSort {
 private int getLeft(int i){
  return 2*i+1;
 }
 private int getRight(int i){
  return 2*i+2;
 }
 public void maxheap(int[] heap,int loc,int size){
  int l=getLeft(loc);
  int r=getRight(loc);
  int largest=loc;
  if(lheap[loc]){
   largest=l;
  }
  if (rheap[largest]) {
   largest=r;
  }
  if(largest!=loc){
   int cache=heap[loc];
   heap[loc]=heap[largest];
   heap[largest]=cache;
   maxheap(heap, largest, size);
  }
 }
 public void buildheap(int[] heap){
  for(int i=heap.length/2;i>=0;i--){
   maxheap(heap, i, heap.length);
  }
 }
 public void sort(int[] heap){
  buildheap(heap);
  for(int i=heap.length-1;i>1;i--){
   int cache=heap[0];
    heap[0]=heap[i];
    heap[i]=cache;
   maxheap(heap, 0,i );
  }
  int cache=heap[0];
   heap[0]=heap[1];
   heap[1]=cache;

 }

 public static void main(String[] args) {
  int[] heap=new int[]{4,1,5,3,7,12,65,7};
  HeapSort hs=new HeapSort();
  hs.sort(heap);
  for (int i = 0; i < heap.length; i++) {
   System.out.println(heap[i]);
  }
 }
}


    
 
 

您可能感兴趣的文章:

  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • java分析html算法(java网页蜘蛛算法示例)
  • 哪里有 DES 算法的Java原码?
  • JAVA有用于数据校验的类吗?象加密算法那样的.
  • Java算法工具 NA_WorkSheet
  • 寻求java加密算法及实例
  • java异或加密算法
  • Java算法包 jga
  • 哪里有《数据结构与算法分析(JAVA版)》的电子书下载,谢了:)
  • 谁给一个树的算法(JAVA)给我?
  • 请问哪里有《数据结构与算法分析(JAVA版)》的电子书下载????
  • 那个大侠可以推荐一本关于java的数据结构和算法的书?  
  • 哪里有 MD5 算法的Java原码?
  • 有没有人用java编过加密算法???
  • 知不知道那里能找到RSA算法的JAVA实现?
  • 请问有没有LZSS加解压缩JAVA算法
  • 看过《数据结构与算法》(java版)谈谈一下感想?
  • 用java做一个“求集合子集的”算法。
  • Web服务器/前端 iis7站长之家
  • 在网络数据传输中,为了降低数据传输量,用哪种算法最好,有哪位大虾帮忙吗?最好有JAVA源代码
  • JAVA简单分组的算法实现
  • JAVA算法起步之快速排序实例
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • java Servlet获取和设置cookie实例代码
  • 万般火急!关于java打印,已经得到printerJob实例,那么怎么通过它得到Pageable实例?
  • 可以有其他两个类的实例同时调用一个java实例的两个方法吗?
  • <java技术手册>与<java实例技术手册>这两本书怎么样?
  • Java单例模式实例简述
  • java web start实例代码COPY不了,怎么办?
  • 请问哪里有《java实例技术手册》的电子书下载?100分赠送!
  • 请教:JAVA中说什么类的实例,那是怎么样的一个概念呢?
  • java实现大数加法(BigDecimal)的实例代码
  • Java究竟能干些什么呢?清高手们列举一些实例出来,跟帖有分.
  • java HashMap的keyset实例
  • java获取当前日期使用实例
  • java之super关键字用法实例解析
  • Java调用DOS实现定时关机的实例
  • java结束进程的实例代码
  • 急!大家谁有类似visio的java实例或代码?
  • java 如何获取对象实例的大小
  • 高分火速求解,请在线朋友回答:java自定义类怎样生成实例数组?( className[] N=new className[X];怎么不行?)
  • 刚学java想试编一个文本编辑器,各位能不能给推荐一些较好的参考程序或实例
  • Java位运算和逻辑运算的区别实例
  • JAVA包装类及自动封包解包实例代码
  • java命名空间java.sql类types的类成员方法: java_object定义及介绍
  • 我想学JAVA ,是买THINK IN JAVA 还是JAVA2核心技术:卷1 好???
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: imageflavor定义及介绍
  • 请问Java高手,Java的优势在那里??,Java主要适合于开发哪类应用程序
  • java命名空间java.lang.management类managementfactory的类成员方法: getcompilationmxbean定义及介绍
  • 如何将java.util.Date转化为java.sql.Date?数据库中Date类型对应于java的哪个Date呢
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getlibrarypath定义及介绍
  • 谁有电子版的《Java编程思想第二版(Thinking in java second)》和《Java2编程详解(special edition java2)》?得到给分
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getstarttime定义及介绍
  • 本人想学java,请问java程序员的待遇如何,和java主要有几个比较强的方向


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3