堆排序

堆

堆是一种树形结构，在排序的过程中，把元素看成是一颗完全二叉树。用数组来表示一颗完全二叉树的话，对于每个节点 i 存在以下关系：
1）父节点 = (i - 1) / 2
2）左孩子 = 2 * i + 1
3）右孩子 = 2 * i + 2

大根堆，小根堆

父节点都比子节点大的堆成为大根堆，用于升序
父节点都比子节点小的堆成为小根堆，用于降序

如图所示：

大根堆 小根堆

算法思路

因此，我们需要把一个树构造成大根堆或小根堆，以大根堆为例子：
1）构造大根堆
2）把根节点和尾节点进行交换，堆的size--
3）把剩余的堆进行调整，重新调整为大根堆
3）重复2，3步骤，直至堆的size为0

1、构造算法

每次插入一颗子节点，都与父节点进行比较，若比父节点大，则与父节点交换后，再重复以上步骤，直至不比父节点大。

  /// 把下标为index的值插入，建立堆
  /// 堆与数组的转换：
  /// 对于当前下标为index的数，其父亲为 (index - 1) / 2
  /// 左节点为 2 * index + 1, 右节点为 2 * index + 2
  public static void heapInsert(int[] arr, int index) {
    // 比父节点大，则交换，直至比父节点小
    while (arr[index] > arr[(index - 1) / 2]) {
      swap(arr, index, (index - 1) / 2);
      index = (index - 1) / 2;
    }
  }

2、调整算法

父节点依次与左右孩子比较，若其父节点小于左右孩子，则与左右孩子较大者交换，然后重复以上步骤，直至父节点大于左右孩子

/// 重新调整为大根堆，size表示：在数组建立了堆，堆的size
  public static void heapify(int arr[], int index, int size) {
    // 左节点
    int left = index * 2 + 1;
    while(left < size) {
      // 右节点
      int right = left + 1;
      // 设左孩子为最大
      int largest = left;
      if (right < size) {
        // 存在右节点，选出其中最大的
        largest = arr[left] > arr[right] ? left : right;
      }
      // 比较父节点和最大子节点的值
      largest = arr[index] > arr[largest] ? index : largest;
      // 若当前节点就是最大的，则调整完毕
      if (largest == index) {
        return;
      }
      // 否则交换
      swap(arr, largest, index);
      // 继续以上过程
      index = largest;
      left = index * 2 - 1;
    }
  }

3、完整代码

  public static void heapSort(int arr[]) {
    if (arr == null || arr.length < 2) {
      return;
    }
    // 建立大根堆
    for(int i = 0; i < arr.length; i++) {
      heapInsert(arr, i);
    }
    int size = arr.length;
    // 将头部换到最后，开始调整，直至size = 0
    swap(arr, 0, --size);
    while(size > 0) {
      heapify(arr, 0, size);
      swap(arr, 0, --size);
    }
  }

  /// 把下标为index的值插入，建立堆
  /// 堆与数组的转换：
  /// 对于当前下标为index的数，其父亲为 (index - 1) / 2
  /// 左节点为 2 * index + 1, 右节点为 2 * index + 2
  public static void heapInsert(int[] arr, int index) {
    // 比父节点大，则交换，直至比父节点小
    while (arr[index] > arr[(index - 1) / 2]) {
      swap(arr, index, (index - 1) / 2);
      index = (index - 1) / 2;
    }
  }

  /// 重新调整为大根堆，size表示：在数组建立了堆，堆的size
  public static void heapify(int arr[], int index, int size) {
    // 左节点
    int left = index * 2 + 1;
    while(left < size) {
      // 右节点
      int right = left + 1;
      // 设左孩子为最大
      int largest = left;
      if (right < size) {
        // 存在右节点，选出其中最大的
        largest = arr[left] > arr[right] ? left : right;
      }
      // 比较父节点和最大子节点的值
      largest = arr[index] > arr[largest] ? index : largest;
      // 若当前节点就是最大的，则调整完毕
      if (largest == index) {
        return;
      }
      // 否则交换
      swap(arr, largest, index);
      // 继续以上过程
      index = largest;
      left = index * 2 - 1;
    }
  }

  public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
  }