Heapify

給一個數組，將它化為 Heap 的結構，也就是兒子都比父親小(大)

有兩種做法，一種是從頭開始掃，一個一個往下交換，複雜度是 O(n log n)

因為掃 n 個，共有 O(log n) 層

public void heapify(int[] A) {
    for (int i = 0; i < A.length; i++) {
        siftup(A, i);
    }
}

//每次都往 father 比較
public void shiftup(int[] A, int k) {
    while (k != 0) {
        int father = (k-1)/2;
        if (A[father] < A[k]) {
            break;
        }
        int temp = A[father];
        A[father] = A[k];
        A[k] = temp;
        k = father;
    }
}

另一種是從 n/2 開始，往下交換，因為 n/2 是倒數第二層，所以時間複雜度會是

(n/2 * 1) + (n/4 * 2) + .... (1 * log n) => O(n)

為什麼 n/2 是倒數第二層？ 可以這樣想：

n/2 * 2 = n 表示 n/2 這層的下一層就會讓整棵樹加起來是 n 個，那不就是倒數第二層嗎？

public void heapify(int[] A) {
    for (int i = A.length/2; i>=0; i--) {
        siftdown(A, i);
    }
}

public void shiftdown(int[] A, int k) {
    // 條件不可以是 (k*2+1 < A.length && k*2+2 < A.legth) 這樣後面的數字會判斷不到
    while (k < A.length) {
        int smallest = k;
        if (k*2+1 < A.length && A[k*2+1] < A[smallest]) {
            smallest = k*2+1;
        }
        if (k*2+2 < A.legth && A[k*2+2] < A[smallest]) {
            smallest = k*2+2;
        }
        if (smallest == k)
            break;
        int temp = A[k];
        A[smallest] = A[k];
        A[k] = temp;
        k = smallest;
    }
}