[JAVA]堆積排序(Heap sort)

2022-06-26 置頂文章
321
0
algorithm
2022-07-01
參考圖片路徑：http://kuring.me/post/algorithm_heap/
package utitled;

import java.util.Arrays;

/** 堆積排序 */
public class HeapSortDemo {
  public static void main(String[] args) {
    int[] arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    Heap heap = new Heap(arr);
    heap.heapSort();
    heap.showTree(); // 堆積排序後，陣列由小到大排序[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
  }
}
/** 大頂堆 */
class Heap {
  private int[] arrBinaryTree;
  public Heap(int[] tree) { this.arrBinaryTree = tree; }
  public void heapSort() {
    buildHeap();
    for (int lastIndex = arrBinaryTree.length - 1; lastIndex >= 0; ) {
      // 每次將堆積頂arr[0]放到陣列的最後，將陣列最後的值放到堆積頂arr[0]
      exchange(0, lastIndex);
      // 若arr[0]的the child大於arr[0]，就繼續往the child的children三者間找出最大值，以這樣的方式進行遞迴...
      // 交換後，原lastIndex即不參與下次比較，索引遞減
      getDownToCheckChildren(0, --lastIndex);
    }
  }
  /* 創建堆積 */
  public void buildHeap() {
    // 找到最後一個父節點的索引，從那裡開始倒著一直到堆積頂(倒著走過每個父結點)，進行getDownToCheckChildren，創建一個堆積
    int lastIndex = arrBinaryTree.length - 1;
    int parentIndex = (lastIndex - 1) / 2;
    for (int i = parentIndex; i >= 0; i--) {
      getDownToCheckChildren(i, lastIndex);
    }
  }
  /**
   * 向下比較
   * @param currentInx 哪個節點的索引
   * @param lastInx 樹的節點個數
   */
  public void getDownToCheckChildren(int currentInx, int lastInx) {
    if (currentInx > lastInx) return;
    // 1. 三個索引，currentInx是當前索引，leftIndex是左孩子的索引，rightIndex是右孩子的索引，
    // 取最大的那個賦給maxIndex
    int leftIndex = 2 * currentInx + 1;  // 左子節點的索引
    int rightIndex = 2 * currentInx + 2; // 右子節點的索引
    int maxIndex = currentInx;
    if (leftIndex <= lastInx && arrBinaryTree[leftIndex] > arrBinaryTree[maxIndex]) maxIndex = leftIndex;
    if (rightIndex <= lastInx && arrBinaryTree[rightIndex] > arrBinaryTree[maxIndex]) maxIndex = rightIndex;
    // 2.若當前值就是最大的那個，也就是最大值索引==當前索引，那麼就沒必要對當前索引去比較與其孩子間的最大值
    // 否則，交換一下兩個值，從maxIndex(孩子索引)處繼續遞迴向下進行比較
    if (maxIndex != currentInx) {
      exchange(maxIndex, currentInx);
      getDownToCheckChildren(maxIndex, lastInx);
    }
  }
  private void exchange(int i, int j) {
    int temp = arrBinaryTree[i];
    arrBinaryTree[i] = arrBinaryTree[j];
    arrBinaryTree[j] = temp;
  }
  public void showTree() {
    System.out.println(Arrays.toString(arrBinaryTree));
  }
}
如有敘述錯誤，還請不吝嗇留言指教，thanks!
回首頁