Heapify

原題連結

題意:把任何一陣列,經過heapify後,使得陣列滿足堆(heap)的條件,即根節點必定小於或大於所有左右子樹的節點。

解題思路:因葉節點無法作sift down,從最小的非葉子節點開始,從後面往前一次作sift down操作,不斷的確認下層保持堆的特性。

對於一個有n節點的樹,其葉節點至少有n/2 -1個。

public class Solution {
    /**
     * @param A: Given an integer array
     * @return: void
     */
    public void heapify(int[] A) {
        for (int i = A.length / 2; i >= 0; i--) {
            siftdown(A, i);
        }
    }

    private void siftdown(int[] A, int k) {
        int smallest = k;
        int len = A.length;
        //k代表是root,接著不斷拿root去與左右子樹的root比,若子樹的值較小,
        //則與k交換,接著k指向到被交換的點,就是不斷去追縱一開始的ROOT
        //請注意,比的是值,smallest紀錄的是當前最小值的index
        while ( k < len) {
            if (k * 2 + 1 < len && A[k * 2 + 1] < A[smallest]) {
                smallest = k * 2 + 1;
            }
            if (k * 2 + 2 < len && A[k * 2 + 2] < A[smallest]) {
                smallest = k * 2 + 2;
            }
            if (smallest == k) {
                break;
            }

            int temp = A[k];
            A[k] = A[smallest];
            A[smallest] = temp;
            k = smallest;
        }
    }
}

results matching ""

    No results matching ""