Java代码为例讲解堆的性质和基本操作以及排序方法

堆的性质
堆是一棵完全二叉树，实际中可以通过一个数组来实现，它最重要的一个性质是：任意节点都小于（大于）等于其子节点。将根节点最小的堆称为最小堆，根节点最大的堆称为最大堆。下图给出了一个最大堆的示例及其数组表示，可以直观地看出每个节点都比它的孩子们都要大。

在上图中可以看到，完全二叉树的节点可以从根节点编号为1开始按顺序排列，对应数组A中的索引（注意此处下标是从1开始的）。给定一个节点i，我们很容易可以得到它的左孩子是2i，右孩子是2i+1，父节点是i/2

堆的基本操作
堆有两种基本操作（下面以最小堆为例）：
插入元素k：直接将k添加到数组最后，然后向上冒泡（bubble-up）调整堆。向上冒泡操作：将要调整的元素与其父节点比较，如果大于其父节点则交换，直到恢复堆的性质。
提取最值：最值即根元素。然后将其删除，令根元素=最后的叶子结点元素，然后从根元素开始向下冒泡（bubble-down）调整堆。向下冒泡操作：每次应该从要调整节点，其左右孩子一共三个节点中选择最小的子节点来交换（如果最小就是其本身就不用交换），直到恢复堆的性质。
实际中经常需要将一个包含n个元素无序数组建立成堆，下面的Heap类中的构造方法将展示如何通过_bubbleDown向下冒泡调整来建堆。堆实质上是一棵完全二叉树，树高总为lognlog⁡n，每种基本操作的耗时操作都在于冒泡调整以满足堆的性质，因此它们的时间复杂度都是O(nlogn)O(nlog⁡n)。
Java示例：

//上浮
public void swim(int k){
  while(k/2>=1 && less(pq[k/2],pq[k])){
    exch(pq,k/2,k);
    k=k/2;
  }
}
//下沉
private void sink() {
  int k=1;
  while(2*k<N){
    int j=2*k;
    if(less(pq[j],pq[j+1])) j++;
    if(less(pq[k],pq[j])) exch(pq,k,j);
    else break;
    k = j;
  }
}

堆排序实现原理
分为两步：
1.把数组排成二叉堆的顺序
2.调换根节点和最后一个节点的位置，然后对根节点进行下沉操作。

实现：
可能我的代码和上面的动画略有出入，不过基本原理差不多。

public class HeapSort extends BaseSort {

  private int N;
  @Override
  public void sort(Comparable[] a) {
    N =a.length-1;
    int k = N/2;
    while(k>=1){
      sink(a,k);
      k--;
    }
    k = 1;
    while(k<=N){
      exch(a,k,N--);
      sink(a,k);
    }
  }
}
赞 (0)

相关推荐

  • Java排序算法总结之堆排序

    Java排序算法总结之堆排序

    本文实例讲述了Java排序算法总结之堆排序.分享给大家供大家参考.具体分析如下: 1991年计算机先驱奖获得者.斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法( Heap Sort ).本文主要介绍堆排序用Java来实现. 堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素.堆排序是不稳定的排序方法,辅助空间为O(1), 最坏

  • 基于Java堆内存的10个要点的总结分析

    Java堆内存的10个要点 .javaoutofmemoryerrorgenerationjvmprofiler编程当我开始学习Java编程时,我不知道什么是堆内存或堆空间,我甚至不知道当对象创建时,它们被放在了哪里.当我开始正式写一些程序后,我会经常遇到java.lang.outOfMemoryError的报错,之后我才开始关注什么是堆内存或者说堆空间(heap space).对大多数程序员都经历过这样的过程,因为学习一种语言是非常容易来的,但是学习基础是非常难的,因为没有什么特定的流程让你学

  • 深入JVM剖析Java的线程堆栈

    深入JVM剖析Java的线程堆栈

    在这篇文章里我将教会你如何分析JVM的线程堆栈以及如何从堆栈信息中找出问题的根因.在我看来线程堆栈分析技术是Java EE产品支持工程师所必须掌握的一门技术.在线程堆栈中存储的信息,通常远超出你的想象,我们可以在工作中善加利用这些信息. 我的目标是分享我过去十几年来在线程分析中积累的知识和经验.这些知识和经验是在各种版本的JVM以及各厂商的JVM供应商的深入分析中获得的,在这个过程中我也总结出大量的通用问题模板. 那么,准备好了么,现在就把这篇文章加入书签,在后续几周中我会给大家带来这一系列的专

  • java自带的工具Jstack截取进程中的堆栈信息

    java自带的工具Jstack截取进程中的堆栈信息

    在Java软件的使用过程中,有时会莫名的出现奇怪的问题.而这些问题常常无法使用日志信息定位,这时我们就需要通过查看进程内部线程的堆栈调用关系来分析问题出在哪里. 举个例子,当我们在做某个操作时,莫名的会弹出多个警告框,其中有些信息是正常的,有些则不是.对于这些错误的警告信息,我们该如何定位是哪个位置的代码出现了错误弹出的框呢? 我们就需要在弹框以后,去查看软件的各个线程,去查找究竟是哪个线程导致了该问题.可是有时因为环境.时间等问题,我们根本不能拿着IDE去调试, 只能通过工具软件拍下内存快照,

  • Java中堆和栈的区别详解

    当一个人开始学习Java或者其他编程语言的时候,会接触到堆和栈,由于一开始没有明确清晰的说明解释,很多人会产生很多疑问,什么是堆,什么是栈,堆和栈有什么区别?更糟糕的是,Java中存在栈这样一个后进先出(Last In First Out)的顺序的数据结构,这就是java.util.Stack.这种情况下,不免让很多人更加费解前面的问题.事实上,堆和栈都是内存中的一部分,有着不同的作用,而且一个程序需要在这片区域上分配内存.众所周知,所有的Java程序都运行在JVM虚拟机内部,我们这里介绍的自然

  • Java使用Deque实现堆栈的方法

    本文实例讲述了Java使用Deque实现堆栈的方法.分享给大家供大家参考.具体如下: import java.util.ArrayDeque; import java.util.Deque; public class IntegerStack { private Deque<Integer> data = new ArrayDeque<Integer>(); public void push(Integer element) { data.addFirst(element); }

  • 输出java进程的jstack信息示例分享 通过线程堆栈信息分析java线程

    复制代码 代码如下: #!/bin/shpro_name=java #process namekeys=`ps -ef |grep "$pro_name" |grep -v "grep" | awk '{print $2}'`nowdate=`date +%Y%m%d%H%M%S` jstackpath="/usr/java/jdk1.6.0_07/bin/jstack"cpulogpath="/home/" for key

  • java内存溢出示例(堆溢出、栈溢出)

    堆溢出: 复制代码 代码如下: /** * @author LXA * 堆溢出 */ public class Heap { public static void main(String[] args) { ArrayList list=new ArrayList(); while(true) { list.add(new Heap()); } } } 报错: java.lang.OutOfMemoryError: Java heap space 栈溢出: 复制代码 代码如下: /** * @a

  • Java编程思想里的泛型实现一个堆栈类 分享

    觉得作者写得太好了,不得不收藏一下. 对这个例子的理解: //类型参数不能用基本类型,T和U其实是同一类型. //每次放新数据都成为新的top,把原来的top往下压一级,通过指针建立链接. //末端哨兵既是默认构造器创建出的符合end()返回true的节点. 复制代码 代码如下: //: generics/LinkedStack.java// A stack implemented with an internal linked structure.package generics; publi

  • 详解Java的堆内存与栈内存的存储机制

    堆与内存优化     今天测了一个项目的数据自动整理功能,对数据库中几万条记录及图片进行整理操作,运行接近到最后,爆出了java.lang.outOfMemoryError,java heap space方面的错误,以前写程序很少遇到这种内存上的错误,因为java有垃圾回收器机制,就一直没太关注.今天上网找了点资料,在此基础上做了个整理.  一.堆和栈 堆-用new建立,垃圾回收器负责回收 1.程序开始运行时,JVM从OS获取一些内存,部分是堆内存.堆内存通常在存储地址的底层,向上排列. 2.堆

  • JAVA算法起步之堆排序实例

    学习堆排序,首先需要明白堆的概念,堆是一个数组.可以近似当做完全二叉树的数组存储方式.但是跟他还有其他的性质,就是类似于二叉排序树.有最大堆跟最小堆之分,最大堆是指根节点的值都大于子节点的值,而最小堆的是根节点的值小于其子节点的值.堆排序一般用的是最大堆,而最小堆可以构造优先队列.堆里面有一个方法是用来维护堆的性质,也就是我们下面代码中的maxheap方法,这是维护最大堆性质的方法,第一个参数就是堆也就是数组,第二个参数是调整堆的具体节点位置,可能这个节点的值不符合最大堆的性质,那么这个值得位置

  • java中堆和栈的区别分析

    堆和栈是Java数据结构里非常重要的概念,本文较为详细的分析了二者之间的区别.供大家参考.具体如下: Java的堆是一个运行时数据区,类的(对象从中分配空间.这些对象通过new.newarray.anewarray和multianewarray等 指令建立,它们不需要程序代码来显式的释放.堆是由垃圾回收来负责的,堆的优势是可以动态地分配内存大小,生存期也不必事先告诉编译器,因为它是在运行时 动态分配内存的,Java的垃圾收集器会自动收走这些不再使用的数据.但缺点是,由于要在运行时动态分配内存,存

  • java堆栈类使用实例(java中stack的使用方法)

    JAVA 中,使用 java.util.Stack 类的构造方法创建对象. public class Stack extends vector 构造方法 : public Stack() 创建一个空 Stack. 方法:  1. public push  (item )  把项 压入栈顶.其作用与 addElement (item ) 相同. 参数 item 压入栈顶的项 . 返回: item 参数 : 2. public pop () 移除栈顶对象,并作为函数的值 返回该对象. 返回:栈顶对象

  • Java实现堆排序(Heapsort)实例代码

    复制代码 代码如下: import java.util.Arrays; public class HeapSort { public static void heapSort(DataWraper[] data){        System.out.println("开始排序");        int arrayLength=data.length;        //循环建堆        for(int i=0;i<arrayLength-1;i++){         

随机推荐