1、首先了解堆是什么

堆是一种数据结构，一种叫做完全二叉树的数据结构。

2、堆的性质

这里我们用到两种堆，其实也算是一种。

最大树：每个节点的值都大于或者等于它的左右子节点的值。

最小树：每个节点的值都小于或者等于它的左右子节点的值。
选择排序_堆排序 - 图1

如上所示，就是两种堆。

如果我们把这种逻辑结构映射到数组中，就是下边这样

选择排序_堆排序 - 图2
这个数组arr逻辑上就是一个堆。

从这里我们可以得出以下性质（重点）
len 当前数组的总长
1.父结点索引：第一个父节点索引地址 i = len/2-1（这里计算机中的除以2，省略掉小数） 例如 父节点3,它的左节点是7,右节点8
2.左孩子索引：2i+1
3.右孩子索引：2i+2
所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：
对于大根堆：arr(i)>arr(2i+1) && arr(i)>arr(2i+2)
对于小根堆：arr(i)<arr(2i+1) && arr(i)<arr(2i+2)

3、堆排序的基本思想

了解了以上内容，我们可以开始探究堆排序的基本思想了。

堆排序的基本思想是：
1、将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。
升序用大根堆，降序就用小根堆
演示网址：
https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

4、代码演示

升序：

  1. public class 堆排序 {
  3.     /*
  4.     i 当前数组的总长
  5.     1.父结点索引：第一个父节点 i = len/2-1（这里计算机中的除以2，省略掉小数） 例如 父节点3,它的左节点是7,右节点8
  6.     2.左孩子索引：2*i+1
  7.     3.右孩子索引：2*i+2
  8.     所以上面两个数组可以脑补成堆结构，因为他们满足堆的定义性质：
  9.     大根堆：arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)
  10.     小根堆：arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)
  11.     */
  13.     public static void main(String[] args) {
  14.         int[] ints = {155, 55, 44, 56, 76, 13, 18, 55};
  15.         int[] ints1 = HeapSort(ints);
  16.         System.out.println(Arrays.toString(ints1));
  17.     }
  19.     public static int[] HeapSort(int[] array) {
  20.         if (array.length < 1) {
  21.             return array;
  22.         }
  23.         int len = array.length;
  24.         // 构建最大堆
  25.         buildMaxHeap(array, len);
  26.         // 循环交换最大堆的顶点和最后一位数的位置
  27.         while (len > 0) {
  28.             // 交换位置，因为此时的最大堆的顶点就是最大值
  29.             swap(array, 0, len - 1);
  30.             // len减一是，最后一位已经是最大值了，不需要在考虑了
  31.             len--;
  32.             // 重新调整最大堆
  33.             heapify(array, 0, len);
  34.         }
  35.         return array;
  36.     }
  39.     // 构建大根堆
  40.     private static void buildMaxHeap(int[] array, int len) {
  41.         // (len - 1) / 2 父节点索引算法，循环构建最大树
  42.         int maxTree = len / 2 - 1;
  43.         for (int i = maxTree; i >= 0; i--) {
  44.             System.out.println("i = " + i);
  45.             // 找到父节点，进行比较判断是否换位
  46.             heapify(array, i, len);
  47.         }
  48.     }
  50.     // 调整成为最大堆 i 头节点的下标
  51.     private static void heapify(int[] array, int i, int len) {
  52.         // 记录父节点的值的指针
  53.         int max = i;
  54.         // 计算出父节点的左节点
  55.         int left = 2 * i + 1;
  56.         // 计算出父节点的右节点
  57.         int right = 2 * i + 2;
  58.         // 如果有左子树len > left，且左子树大于父节点，则将最大指针指向左子树
  59.         if (len > left && array[left] > array[max]) {
  60.             max = left;
  61.         }
  62.          //如果有右子树len > right，且右子树大于父节点，则将最大指针指向右子树
  63.         if (len > right && array[right] > array[max]) {
  64.             max = right;
  65.         }
  66.         // 说明父节点不是最大的，此时进行交换位置
  67.         if (max != i) {
  68.             swap(array, max, i);
  69.             // 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整
  70.             heapify(array, max, len);
  71.         }
  72.     }
  74.     /**
  75.      * 交换索引
  76.      *
  77.      * @param arr
  78.      * @param i
  79.      * @param j
  80.      */
  81.     private static void swap(int[] arr, int i, int j) {
  82.         int temp = arr[i];
  83.         arr[i] = arr[j];
  84.         arr[j] = temp;
  85.     }
  86. }