package org.rev.algorithm;

/**
 * 堆排序，时间复杂度为O(nlogn)，是利用堆的性质进行的一种选择排序。
 * 
 * 大顶堆是一个完全二叉树，所有的父节点都大于或等于它的左右子节点，即a[i]>=a[2i+1]&&a[i]>=a[2i+2]。 
 *(小顶堆是父节点<=子节点)
 * 
 * 对于完全二叉树，任意节点a[i]的父节点的索引值是(i-1) / 2 向下取整。
 * 
 * 1.对于序列a[0]-a[n-1]，构建大顶堆，堆顶a[0]为最大值。
 * 
 * 2. 交换堆顶a[0]和最后一个元素a[n-1]，此时，a[0]-a[n-2]是无序的，a[n-1]是有序的。
 * 
 * 3. 交换后的a[0]可能是违反大顶堆的，需要再次构建大顶堆，并交换a[0]和a[n-2]。
 *    此时a[0]-a[n-3]是无序的，a[n-2]-a[n-1]是有序的。
 * 
 * 4. 如此循环n次，i次循环后，a[n-i]-a[n-1]都是有序的，直到i=n，此时a[0]-a[n-1]已是有序数列。
 * 
 */
public class HeapSort {

  public static void main(String[] args) {
    int[] data = {39, 11, 38, 97, 86, 37, 12, 4, 51, 18};
    // 堆排序
    HeapSort hs = new HeapSort();
    hs.heapSort(data);
    System.out.println("排序之后：");
    hs.print(data);
  }

  /**
   * 堆排序
   */
  public void heapSort(int[] data) {
    for (int i = 0; i < data.length; i++) { // 循环建堆
      buildMaxHeap(data, data.length - 1 - i); // 建堆，排序结果是升序
      // buildMinHeap(data, data.length - 1 - i); // 建堆，排序结果是降序
      swap(data, 0, data.length - 1 - i); // 交换堆顶和最后一个元素
      print(data);
    }
  }

  /**
   * 对数组data[0]到data[lastIndex]构建大顶堆
   * 
   * @param data 等待构建大顶堆的数组
   * @param lastIndex 数组中最后一个元素的索引值
   */
  public void buildMaxHeap(int[] data, int lastIndex) {

    for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // 从最后一个元素的父节点开始
      int k = i; // 保存当前正在判断的节点

      while (2 * k + 1 <= lastIndex) { // 若节点data[k]的左子节点存在
         // tmpIndex记录较大节点的索引值，初始值为当前节点的左子节点的索引值
        int tmpIndex = 2 * k + 1; 

        // 比较左右子节点哪个大
        // 满足此条件说明右子节点存在，否则此时tmpIndex应该等于 lastIndex
        if (tmpIndex < lastIndex) { 
          // (data[2*k+1] <data[2*k+2])，左子节点小于右子节点
          if (data[tmpIndex] < data[tmpIndex + 1]) { 
            // tmpIndex总是记录较大节点的索引值
            tmpIndex++;
          }
        }

        // 使最大值位于父节点
        if (data[k] < data[tmpIndex]) {
          swap(data, k, tmpIndex); // 交换两个元素在数组中的位置
          k = tmpIndex;
        } else {
          break;
        }

      }
    }
  }


  /**
   * 对数组data[0]到data[lastIndex]构建小顶堆
   * 
   * @param data 等待构建小顶堆的数组
   * @param lastIndex 数组中最后一个元素的索引值
   */
  public void buildMinHeap(int[] data, int lastIndex) {

    for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // 从最后一个元素的父节点开始
      int k = i; // 保存当前正在判断的节点

      while (2 * k + 1 <= lastIndex) { // 若当前节点的子节点data[2k+1]存在
        // tmpIndex，记录较小节点的索引值，初始值为当前节点的左子节点的索引值
        int tmpIndex = 2 * k + 1; 

        // 比较左右子节点哪个小
        // 满足此条件说明右子节点存在，否则此时tmpIndex应该等于 lastIndex
        if (tmpIndex < lastIndex) { 
          // (data[2*k+1] >data[2*k+2])，左子节点大于右子节点
          if (data[tmpIndex] > data[tmpIndex + 1]) { 
            // tmpIndex总是记录较小节点的索引值
            tmpIndex++;
          }
        }

        // 使小值位于父节点
        if (data[k] > data[tmpIndex]) {
          swap(data, k, tmpIndex); // 交换两个元素在数组中的位置
          k = tmpIndex;
        } else {
          break;
        }

      }
    }
  }


  /**
   * 交换两个元素在数组中的位置
   * 
   * @param data
   * @param i
   * @param j
   */
  public void swap(int[] data, int i, int j) {
    if (i == j) {
      return;
    }

    /*
     * int tmp = data[i]; 
     * data[i] = data[j]; 
     * data[j] = tmp;
     * 
     * 下面三句代码和上面注释掉的三句效果一样，时间换空间的游戏。
     */
    data[i] = data[i] + data[j];
    data[j] = data[i] - data[j];
    data[i] = data[i] - data[j];

  }

  /*
   * 输出数组中的元素
   */
  private void print(int[] data) {

    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }

}

       堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。

       堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。

参考 http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html

堆排序(JAVA)