public class HeapSort {
  private int[] numbers;
  private int length;
  public HeapSort(int[] numbers) {
    this.numbers = numbers;
    this.length = numbers.length;
  }
  /**
   * 調(diào)整二叉樹
   * 如果父節(jié)點(diǎn)編號(hào)為x, 那么左子節(jié)點(diǎn)的編號(hào)是2x, 右子節(jié)點(diǎn)的編號(hào)是2x+1
   * 節(jié)點(diǎn)編號(hào)從1開始, 對(duì)應(yīng)數(shù)組中的索引是編號(hào)-1
   * @param nodeId 節(jié)點(diǎn)編號(hào), 從1開始
   */
  public void adjust(int nodeId) {
    int swapId;
    int flag = 0; //是否需要繼續(xù)向下調(diào)整
    while(nodeId * 2 <= this.length && flag == 0) {
      //首先判斷它和左子節(jié)點(diǎn)的關(guān)系, 并用swapId記錄值較小的節(jié)點(diǎn)編號(hào)(最大堆是記錄較大的)
      int index = nodeId - 1; //節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中數(shù)字的索引
      int leftChild = nodeId * 2 - 1; //左子節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中數(shù)字的索引
      int rightChild = nodeId * 2; //右子節(jié)點(diǎn)對(duì)應(yīng)數(shù)組中數(shù)字的索引
      if(numbers[index] < numbers[leftChild]) {
        swapId = nodeId * 2;
      } else {
        swapId = nodeId;
      }
      //如果有右子節(jié)點(diǎn), 再與右子節(jié)點(diǎn)比較
      if(nodeId * 2 + 1 <= this.length) {
        if(numbers[swapId - 1] < numbers[rightChild])
          swapId = nodeId * 2 + 1;
      }
      //如果最小的節(jié)點(diǎn)編號(hào)不是自己, 說明子節(jié)點(diǎn)中有比父節(jié)點(diǎn)更小的
      if(swapId != nodeId) {
        swap(swapId, nodeId);
        nodeId = swapId;
      } else {
        flag = 1;
      }
    }
  }
  /**
   * 交換兩個(gè)節(jié)點(diǎn)的值
   * @param nodeId1
   * @param nodeId2
   */
  public void swap(int nodeId1, int nodeId2) {
    int t = numbers[nodeId1 - 1];
    numbers[nodeId1 - 1] = numbers[nodeId2 - 1];
    numbers[nodeId2 - 1] = t;
  }
  /**
   * 創(chuàng)建最大堆
   */
  public void createMaxHeap() {
    //從最后一個(gè)非葉節(jié)點(diǎn)到第一個(gè)節(jié)點(diǎn)依次向上調(diào)整
    for(int i = this.length / 2; i >= 1; i--) {
      adjust(i);
    }
  }
  public static void main(String[] args) {
    int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };
    for(int x = 0; x < numbers.length; x++) {
      System.out.print(numbers[x] + " ");
    }
    System.out.println();
    HeapSort heap = new HeapSort(numbers);
    heap.createMaxHeap();
  }
}

public void sort() {
  while(this.length > 1) {
    swap(1, this.length);
    this.length--;
    adjust(1);
  }
  for(int x = 0; x < numbers.length; x++) {
    System.out.print(numbers[x] + " ");
  }
}