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;
  }
}

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

# 堆排序（HeapSort） # java # 堆排序 # HeapSort # Java数据结构之优先级队列(堆)图文详解 # Java 数据结构与算法系列精讲之二叉堆 # Java深入了解数据结构之优先级队列(堆) # 深入了解Java数据结构和算法之堆 # Java数据结构中堆的向下和向上调整解析 # Java 数据结构之堆的概念与应用 # java数据结构-堆实现优先队列 # Java 超详细讲解数据结构中的堆的应用 # 子树 # 大堆 # 都是 # 数据结构 # 树上 # 是一种 # 有可能 # 最重要 # 希望能 # 实际情况 # 谢谢大家 # 不稳定 # 并与 # 为大 # 棵树 # 则需 # 把该 # 降序 # 二叉树 # 不小于

返回目录在线咨询

上一篇：使用云开建站平台，能否自定义网站的域名和页面布局？
下一篇：比较有名的diy制作网站,如何自制网站？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

java 数据结构之堆排序（HeapSort）详解及实例

您的项目需求