堆排序

    堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。既然是堆排序，自然需要先建立一个堆，而建堆的核心内容是调整堆，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）。调堆的过程应该从最后一个非叶子节点开始


堆排序包括两个步骤
  (a)初始堆(堆的定义：(1)堆是一个完全二叉树(2)根结点的值或者大于左右子树的值或者小于左右子树的值(3)左右子树也是一个堆)
  (b)调整堆(当初始小顶堆之后，堆顶元素是最小的元素，取出最小的元素与最后一个元素相交换，再把剩下n-1个元素调整成堆,依次调整直到1为止)
非终端节点调整 初始堆时从n/2向上调整成堆 把第一个元素与最后一个元素交换之后从第1个元素开始调整成新堆

public class HeapSort {
 public static void main(String[] args) {
  HeapSort h = new HeapSort();
  int num[] = new int[] { 1, 3, 4, 5, 7, 2, 6, 8, 0 };
  h.heapSort(num, num.length);
  for (int x = 0; x < num.length; x++) {
   System.out.print(num[x] + " ");
  }
 }
 void AdjustHeap(int A[], int hLen, int i) {
  int left = LeftChild(i); // 节点i的左孩子
  int right = RightChild(i); // 节点i的右孩子节点
  int largest = i;
  int temp;
  while (left < hLen || right < hLen) {
   if (left < hLen && A[largest] < A[left]) {
    largest = left;
   }
   if (right < hLen && A[largest] < A[right]) {
    largest = right;
   }
   if (i != largest) // 如果最大值不是父节点
   {
    temp = A[largest]; // 交换父节点和和拥有最大值的子节点交换
    A[largest] = A[i];
    A[i] = temp;
    i = largest; // 新的父节点，以备迭代调堆
    left = LeftChild(i); // 新的子节点
    right = RightChild(i);
   } else {
    break;
   }
  }
 }
 private int RightChild(int i) {
  return 2 * i + 2;
 }
 private int LeftChild(int i) {
  return 2 * i + 1;
 }
 /*
  * 输入：数组A，堆的大小hLen 功能：建堆
  */
 void BuildHeap(int A[], int hLen) {
  int i;
  int begin = hLen / 2 - 1; // 最后一个非叶子节点
  for (i = begin; i >= 0; i--) {
   AdjustHeap(A, hLen, i);
  }
 }
 /*
  * 输入：数组A，待排序数组的大小aLen 功能：堆排序
  */
 void heapSort(int A[], int aLen) {
  int hLen = aLen;
  int temp;
  BuildHeap(A, hLen); // 建堆
  while (hLen > 1) {
   temp = A[hLen - 1]; // 交换堆的第一个元素和堆的最后一个元素
   A[hLen - 1] = A[0];
   A[0] = temp;
   hLen--; // 堆的大小减一
   AdjustHeap(A, hLen, 0); // 调堆
  }
 }
}