Heapify

Question

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i 2 + 1] is the left child of A[i] and A[i 2 + 2] is the right child of A[i].

Solution

我記得這題第一次寫沒有寫出來。第二次寫寫出了 siftdown，但寫 siftup 還是寫不出。

主要原因是在寫 siftup 的過程中，我讓 for loop 從尾巴走回來，不正確的原因在於，siftup 要一直去跟自己的 parent 比較，在每個 iteration 中，要確認的是所有在當前的 index 之前的 node 都已經變成 min heap 了，所以必須從上面走下來。

所以，如果是寫 siftdown，for loop 可以從 A.length / 2 往回走。為什麼呢？因為 siftdown 要確保的是，從當前這個 index 往下的所有 node 都是 min heap，而在 heap 中，會有一半的 node 是 leaf，因此可以從中間往回走

siftup

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

    public void siftup(int[] A, int childIndex) {
        while (childIndex > 0) {
            int parentIndex = (childIndex - 1) / 2;
            if (A[parentIndex] < A[childIndex]) {
                break;
            }

            int temp = A[parentIndex];
            A[parentIndex] = A[childIndex];
            A[childIndex] = temp;

            childIndex = parentIndex;
        }
    }

siftdown

    public void heapify(int[] A) {
        // write your code here

        for (int i = A.length/2; i >= 0; i--) {
            siftdown(A, i);
        }
    }

    public void siftdown(int[] A, int k) {
        while (k < A.length) {
            int leftIndex = (2*k + 1 < A.length)? 2*k + 1: -1;
            int rightIndex = (2*k + 2 < A.length)? 2*k + 2: -1;

            int left = (leftIndex != -1)? A[leftIndex] : Integer.MAX_VALUE;
            int right = (rightIndex != -1)? A[rightIndex] : Integer.MAX_VALUE;
            if (right >= A[k] && left >= A[k]) {
                break;
            }

            int changeIndex = (left >= right) ? rightIndex : leftIndex;
            int temp = A[k];
            A[k] = A[changeIndex];
            A[changeIndex] = temp;

            k = changeIndex;
        }
    }