大顶堆：每个节点的值都大于或**等于**其左右孩子节点的值，
小顶堆：每个节点的值都小于或等于其左右孩子节点的值，
二叉树性质5 ： 一个完全二叉树，如果i=1,则节点i是二叉树的根，无双亲；如果i>2,则其双亲是节点 2/i;
即 i 的左右子节点分别是2i 和 2i+1；

代码

  1. /**
  2.  * @Description: 堆排序
  3.  * 大顶堆：每个节点的值都大于或等于其左右孩子节点的值，
  4.  * 小顶堆：每个节点的值都小于或等于其左右孩子节点的值，
  5.  * @Author: lizhouwei
  6.  * @CreateDate: 2018/6/23 11:16
  7.  */
  8. public class HeapSort {
  10.     public static void heapSort(Integer[] arr) {
  11.         if (arr == null || arr.length == 0) {
  12.             return;
  13.         }
  14.         SortUtil.printArray("堆排序前", arr);
  16.         for (int i = arr.length / 2; i > 0; i--) {
  17.             heapify(arr, i, arr.length);
  18.         }
  19.         for (int i = arr.length - 1; i > 0; i--) {
  20.             SortUtil.swap(arr, 0, i);
  21.             heapify(arr, 0, i);
  22.         }
  23.         SortUtil.printArray("堆排序后", arr);
  24.     }
  26.     private static void heapify(Integer[] arr, int index, int size) {
  27.         int left = index * 2 + 1;
  28.         int right = index * 2 + 2;
  29.         int largest = index;
  30.         while (left < size) {
  31.             if (arr[left] > arr[index]) {
  32.                 largest = left;
  33.             }
  34.             if (right < size && arr[right] > arr[largest]) {
  35.                 largest = right;
  36.             }
  37.             if (largest == index) {
  38.                 break;
  39.             }
  40.             SortUtil.swap(arr, index, largest);
  41.             index = largest;
  42.             left = index * 2 + 1;
  43.             right = index * 2 + 2;
  44.         }
  45.     }
  46. }

时间复杂度分析

在构建堆的过程中，因为是完全二叉树从最下层最右边的非终端结点开始构建，将它与其它孩子进行比较，如果符合交换条件，再进行交换，对于每个非终端节点来说，其实进行两次比较和互换操作，因此整个构建堆的时间复杂度为堆排序 - 图1。
在正式排序时，第i次取堆顶记录重建堆需要用堆排序 - 图2的时间（完全二叉树的某个节点到根节点的距离为堆排序 - 图3）,并且需要取 n-1 次堆顶记录，因此重建堆的时间复杂度为 堆排序 - 图4；
所以总体来说 堆排序的时间复杂度为堆排序 - 图5；由于堆排序对原始记录的排序状态并不关心，因此无论最好、最坏和平均复杂度均为堆排序 - 图6。
空间复杂度上，它只有一个用来交换的暂存单元，不过由于记录的比较与交换时跳跃式进行的，因此堆排序也是一种不稳定的排序方法。