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

 更新时间:2016年06月08日 12:01:34   作者:林寿山   我要评论
堆数据结构可以看作一颗完全二叉树,因而又被成为二叉堆,这里我们以Java代码为例讲解堆的性质和基本操作以及排序方法,需要的朋友可以参考下

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

201668115430035.jpg (815×272)

在上图中可以看到,完全二叉树的节点可以从根节点编号为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);
    }
  }
}

相关文章

  • Spring+MyBatis实现数据读写分离的实例代码

    Spring+MyBatis实现数据读写分离的实例代码

    本篇文章主要介绍了Spring+MyBatis实现数据读写分离的实例代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-07-07
  • SpringBoot跨域Jsonp和Cors的方法

    SpringBoot跨域Jsonp和Cors的方法

    这篇文章主要介绍了SpringBoot跨域Jsonp和Cors的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2019-08-08
  • SSM框架+Plupload实现分块上传大文件示例

    SSM框架+Plupload实现分块上传大文件示例

    这篇文章主要介绍了SSM框架+Plupload实现分块上传示例(Spring+SpringMVC+MyBatis+Plupload),将用户选中的文件(可多个)分隔成一个个小块,依次向服务器上传,有兴趣的可以了解一下。
    2017-03-03
  • JavaWeb项目中classpath路径详解

    JavaWeb项目中classpath路径详解

    今天小编就为大家分享一篇关于JavaWeb项目中classpath路径详解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
    2018-12-12
  • spring security自定义认证登录的全过程记录

    spring security自定义认证登录的全过程记录

    这篇文章主要给大家介绍了关于spring security自定义认证登录的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧。
    2017-12-12
  • 浅谈将JNI库打包入jar文件

    浅谈将JNI库打包入jar文件

    这篇文章主要介绍了浅谈将JNI库打包入jar文件,具有一定借鉴价值,需要的朋友可以参考下。
    2017-12-12
  • 浅谈利用Session防止表单重复提交

    浅谈利用Session防止表单重复提交

    这篇文章主要介绍了浅谈利用Session防止表单重复提交,简单介绍表单重复提交的情况,分析,以及解决方法代码示例,具有一定借鉴价值,需要的朋友可以了解下。
    2017-12-12
  • java使用es查询的示例代码

    java使用es查询的示例代码

    本篇文章主要介绍了java使用es查询的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2018-01-01
  • 模仿百度红包福袋界面实例代码

    模仿百度红包福袋界面实例代码

    新年到新年到,红包抢不停。在我抢红包的时候意外的发现了百度的福袋界面挺不错的,于是抽时间专门写篇文章来完成百度红包界面吧
    2016-02-02
  • javaweb登录验证码的实现方法

    javaweb登录验证码的实现方法

    这篇文章主要为大家详细介绍了javaweb登录验证码的实现方法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-11-11

最新评论