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

1 堆排序

堆是一种重要的数据结构,分为大根堆和小根堆,是完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1),如果它有左子树,那么左子树的位置是2i+1,如果有右子树,右子树的位置是2i+2,如果有父节点,父节点的位置是(n-1)/2取整。最大堆的任意子树根节点不小于任意子结点,最小堆的根节点不大于任意子结点。

所谓堆排序就是利用堆这种数据结构的性质来对数组进行排序,在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的性质可知,最大的值一定在堆顶。堆排序一种不稳定的排序算法,其时间复杂度为O(nlogn)。

2 算法思想

(1)构建最大堆;
(2)选择顶,并与第0位置元素交换;
(3)由于步骤(2)的的交换可能破环了最大堆的性质,即第0位置的元素不再是最大元素,则需要调用maxHeap调整堆(沉降法),根据实际情况重复步骤(2)。

堆排序中最重要的算法就是maxHeap,该函数假设一个元素的两个子节点都满足最大堆的性质(即左、右子树都是最大堆),只有根元素可能违反最大堆性质,那么把该元素以及左右子节点的最大元素找出来,如果该元素已经最大,那么整棵树都是最大堆,程序退出,否则交换根元素与最大元素的位置,继续调用maxHeap构建最大元素所在的子树。

3 Java代码

public class HeapSort {
  public static void main(String[] args) {
    int[] arr = {3, 2, 1, 0, -1, -2, -3};
    System.out.println("Before heap:");
    printArray(arr);
    heapSort(arr);
    System.out.println("After heap sort:");
    printArray(arr);
  }

  public static void heapSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    buildMaxHeap(arr); //构建最大堆
    for (int i = arr.length - 1; i >= 1; i--) {
      exchangeElements(arr, 0, i); //交换堆顶和第0位置元素
      maxHeap(arr, i, 0); //因为交换元素后,有可能违反堆的性质,所以沉降元素
    }
  }

  private static void buildMaxHeap(int[] arr) { //构建最大堆
    if (arr == null || arr.length <= 1) {
      return;
    }
    int half = arr.length / 2;
    for (int i = half; i >= 0; i--) {
      maxHeap(arr, arr.length, i);
    }
  }

  private static void maxHeap(int[] arr, int heapSize, int index) {
    int left = index * 2 + 1; //左子树上的元素
    int right = index * 2 + 2; //右子树上的元素
    int largest = index; //初始化最大元素
    if (left < heapSize && arr[left] > arr[index]) {
      largest = left;
    }
    if (right < heapSize && arr[right] > arr[largest]) {
      largest = right;
    }
    if (index != largest) { //判断根元素是否为最大元素
      exchangeElements(arr, index, largest);
      maxHeap(arr, heapSize, largest);
    }
  }

  public static void printArray(int[] arr) { //打印数组
    System.out.print("{");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i]);
      if (i < arr.length - 1) {
        System.out.print(", ");
      }
    }
    System.out.println("}");
  }

  public static void exchangeElements(int[] arr, int index1, int index2) { //交换元素
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
  }
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

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

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

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

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

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

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

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

  • 深入解析堆排序的算法思想及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版实现

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

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

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

随机推荐