深入解析堆排序的算法思想及Java代码的实现演示

一、基础知识
我们通常所说的堆是指二叉堆,二叉堆又称完全二叉树或者叫近似完全二叉树。二叉堆又分为最大堆和最小堆。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。数组可以根据索引直接获取元素,时间复杂度为O(1),也就是常量,因此对于取值效率极高。
最大堆的特性如下:

  • 父结点的键值总是大于或者等于任何一个子节点的键值
  • 每个结点的左子树和右子树都是一个最大堆

最小堆的特性如下:

  • 父结点的键值总是小于或者等于任何一个子节点的键值
  • 每个结点的左子树和右子树都是一个最小堆

二、算法思想
1.最大堆的算法思想是:
先将初始的R[0…n-1]建立成最大堆,此时是无序堆,而堆顶是最大元素
再将堆顶R[0]和无序区的最后一个记录R[n-1]交换,由此得到新的无序区R[0…n-2]和有序区R[n-1],且满足R[0…n-2].keys ≤ R[n-1].key
由于交换后,前R[0…n-2]可能不满足最大堆的性质,因此再调整前R[0…n-2]为最大堆,直到只有R[0]最后一个元素才调整完成。
最大堆排序完成后,其实是升序序列,每次调整堆都是要得到最大的一个元素,然后与当前堆的最后一个元素交换,因此最后所得到的序列是升序序列。
2.最小堆的算法思想是:
先将初始的R[0…n-1]建立成最小堆,此时是无序堆,而堆顶元素是最小的元素
再将堆顶R[0]与无序区的最后一个R[n-1]交换,由此得到新的无序堆R[0…n-2]和有序堆R[n-1],且满足R[0…n-2].keys >= R[n-1].key
由于交换后,前R[0…n-2]可能不满足最小堆的性质,因此再调整前R[0…n-2]为最小堆,直到只有R[0]最后一个元素才调整完成
最小堆排序完成后,其实是降序序列,每次调整堆都是要得到最小的一个元素,然后与当前无序堆的最后一个元素交换,所以所得到的序列是降序的。
提示:堆排序的过程,其实就是不断地扩大有序区,然后不断地缩小无序区,直到只有有序区的过程。

三、排序过程分析
因为算法比较抽象,这里直接通过举个小例子来说明堆排序的过程是如何的。下面我们用这个无序序列采用最大堆的进行堆排序,所得到的序列就是升序序列(ASC)。
无序序列:89,-7,999,-89,7,0,-888,7,-7
第一步:初始化建成最大堆:

第二步:将堆顶最大元素999与无序区的最后一个元素交换,使999成为有序区。交换后,-7成为堆顶,由于-7并不是无序区中最大的元素,因此需要调整无序区,使无序区中最大值89成为堆顶,所以-7与89交换。交换后导致89的右子树不满足最大堆的性质,因此要对右子树调整成最大堆,所以-7要与0交换,如下图:

从图中看到,当-7成89交换后,堆顶是最大元素了,但是-7的左孩子是0,右孩子是-888,由于-7<0,导致-7这个结点不满足堆的性质,因此需要调整它。所以,0与-7交换。
然后不断重复着第二步的过程,直到全部成为有序区。
最后:所得到的是升序序列

四、时间复杂度
堆排序的时间,主要由建立初始堆和反复调整堆这两部分的时间开销构成.由于堆排序是不稳定的,它得扭到的时间复杂度会根据实际情况较大,因此只能取平均时间复杂度。
平均时间复杂度为:O( N * log2(N) )
堆排序耗时的操作有:初始堆 + 反复调整堆,时间复杂度如下:
1.初始建堆:每个父节点会和左右子节点进行最多2次比较和1次交换,所以复杂度跟父节点个数有关。根据2x <= n(x为n个元素可以折半的次数,也就是父节点个数),得出x = log2n。即O ( log2n )
2.反复调整堆:由于初始化堆过程中,会记录数组比较结果,所以堆排序对原序列的数组顺序并不敏感,最好情况和最坏情况差不多。需要抽取 n-1 次堆顶元素,每次取堆顶元素都需要重建堆(O(重建堆) < O(初始堆))。所以小于 O(n-1) * O(log2n)
使用建议:
由于初始化堆需要比较的次数较多,因此,堆排序比较适合于数据量非常大的场合(百万数据或更多)。由于高效的快速排序是基于递归实现的,所以在数据量非常大时会发生堆栈溢出错误。

五、Java示例代码

public class HeapSort{
 private static int[] sort=new int[]{1,0,10,20,3,5,6,4,9,8,12,
   17,34,11};

 public static void main(String[] args){
  buildMaxHeapify(sort);
  heapSort(sort);
  print(sort);
 }

 private static void buildMaxHeapify(int[] data){
//没有子节点的才需要创建最大堆,从最后一个的父节点开始
  int startIndex=getParentIndex(data.length-1);
//从尾端开始创建最大堆,每次都是正确的堆
  for(int i=startIndex;i>=0;i--){
   maxHeapify(data,data.length,i);
  }
 }

 /**
  *创建最大堆
  *
  *@paramdata
  *@paramheapSize需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了
  *@paramindex当前需要创建最大堆的位置
  */
 private static void maxHeapify(int[] data,int heapSize,int index){
//当前点与左右子节点比较
  int left=getChildLeftIndex(index);
  int right=getChildRightIndex(index);

  int largest=index;
  if(left<heapSize&&data[index]<data[left]){
   largest=left;
  }
  if(right<heapSize&&data[largest]<data[right]){
   largest=right;
  }
//得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整
  if(largest!=index){
   int temp=data[index];
   data[index]=data[largest];
   data[largest]=temp;
   maxHeapify(data,heapSize,largest);
  }
 }

 /**
  *排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的
  *
  *@paramdata
  */
 private static void heapSort(int[] data){
//末尾与头交换,交换后调整最大堆
  for(int i=data.length-1;i>0;i--){
   int temp=data[0];
   data[0]=data[i];
   data[i]=temp;
   maxHeapify(data,i,0);
  }
 }

 /**
  *父节点位置
  *
  *@paramcurrent
  *@return
  */
 private static int getParentIndex(int current){
  return(current-1)>>1;
 }

 /**
  *左子节点position注意括号,加法优先级更高
  *
  *@paramcurrent
  *@return
  */
 private static int getChildLeftIndex(int current){
  return(current<<1)+1;
 }

 /**
  *右子节点position
  *
  *@paramcurrent
  *@return
  */
 private static int getChildRightIndex(int current){
  return(current<<1)+2;
 }

 private static void print(int[] data){
  int pre=-2;
  for(int i=0;i<data.length;i++){
   if(pre<(int)getLog(i+1)){
    pre=(int)getLog(i+1);
    System.out.println();
   }
   System.out.print(data[i]+"|");
  }
 }

 /**
  *以2为底的对数
  *
  *@paramparam
  *@return
  */
 private static double getLog(double param){
  return Math.log(param)/Math.log(2);
 }
}
(0)

相关推荐

  • java堆排序原理及算法实现

    从堆排序的简介到堆排序的算法实现等如下: 1. 简介 堆排序是建立在堆这种数据结构基础上的选择排序,是原址排序,时间复杂度O(nlogn),堆排序并不是一种稳定的排序方式.堆排序中通常使用的堆为最大堆. 2. 堆的定义 堆是一种数据结构,是一颗特殊的完全二叉树,通常分为最大堆和最小堆.最大堆的定义为根结点最大,且根结点左右子树都是最大堆:同样,最小堆的定义为根结点最小,且根结点左右子树均为最小堆. 最大堆满足其每一个父结点均大于其左右子结点,最小堆则满足其每一个父结点均小于其左右子结点. 3.

  • java 数据结构之堆排序(HeapSort)详解及实例

    1 堆排序 堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整.最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点. 所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的

  • Java堆排序算法详解

    堆是数据结构中的一种重要结构,了解"堆"的概念和操作,可以帮助我们快速地掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+

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

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

  • Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • 详解堆排序算法原理及Java版的代码实现

    概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

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

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

  • Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

    本文实例汇总了Java各种排序算法.分享给大家供大家参考,具体如下: 1. 冒泡排序: public class SortTest { public static void main(String[] args) { int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345}; show(a); bubbleSort(a); show(a); } private static void bubbleSo

  • 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++){         

  • 堆排序算法的讲解及Java版实现

    堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆

随机推荐