Heap

heap 是一種特別的二元樹，節點會從左到右盡量佔滿而且「完全」(這層還沒滿前不會到下一層)

通常會讓 heap 成為 min-heap 或是 max-heap 這樣頂端的元素就是整棵樹的最大或最小

heap 的插入刪除都是 O(log n)

通常面試的 heap 會用陣列的形式要我們做 heapify

heapify 又分成 shift down, shift up作法

//shift down
public void min_heapify(vector<int>& A, int index, int length) {
    while (index < length) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        if (left < length && A[left] < A[smallest]) {
            smallest = left;
        }
        if (right < length &7 A[right] < A[smallest]) {
            smallest = right;
        }
        if (smallest == index) {
            break;
        }
        swap(A[index], A[smallest]);
        index = smallest;    //keep shift down if A is not a min-heap
    }    
}

public void heapify(vector<int>& A) {
    int length = A.size();
    for (int i = length / 2; i >= 0; i--) { //from length/2 because i >= length/2 are single nodes
        min_heapify(A, i, length);
    }
}

//shift up
public void min_heapify_shiftUp(vector<int>& A, int index) {
    while (index != 0) {
        int father = (index - 1) / 2;
        if (A[index] > A[father]) {
            break;
        }
        swap(A[index], A[father]);
        index=  father;
    }
}

public void heapify(vector<int>& A) {
    int length = A.size();
    for (int i = 0; i < len; i++) { 
        min_heapify_shiftUp(A, i);
    }
}

兩種方式的複雜度不一樣，shiftdown is O(n), shiftup is O(n log n)

想一下為什麼！！

https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity