今天要來介紹 heap 的 operation。
一個 max-heap class 需要有的操作有：

1. insert x
2. delete max
3. heapify(adjust)
4. find-max
5. build-heap (top-down bottom-up)
6. merge two heap

heap class：這次用 Java 實作

attribute:

一個 Array 代表 heap 即可。另外再用一個 int 來代表目前 heap 的長度。

另外，因為 Array 中，root 編號為 0，因此我們必須調整一下 complete Binary tree 的編號規則。

若目前有 N 個節點，陣列編號從 0 ~ N - 1

1. 如果某節點編號為 i，則其左子點編號為 2i + 1，右子點編號為 2i + 2，其中子點的編號必須小於 N
2. 如果某節點編號為 i，則其父點編號為 floor((i - 1) / 2)，其中父點的編號必須大於等於 0

1. insert x: O(logn)

    public void insert(int x){
        heap[++size] = x;
        int child = size;
        int parent = (size - 1) / 2;

        while(parent >= 0){
            if(heap[parent] < x){
                heap[child] = heap[parent];
                child = parent;
                if(child == 0){
                    parent = -1;
                }else{
                    parent = (parent - 1) / 2;
                }
            }else{
                break;
            }
        }
        //System.out.printf("input %d into heap\n", x);
        heap[child] = x;
    }

跟昨天介紹的一樣，先將節點放入 size + 1 後的位置，然後再向上調整，要注意的是，程式碼中並不需要真的有「調換的動作」，反倒是將需要移動的父點下移後，確定位置，再將新插入的值放入該位置。
而因為新增的動作最多就是從樹葉移動到樹根，因此時間是 O(H) = O(logn)。

2. heapify, Adjust: O(logn)

    public void adjust(int node){
        int x = heap[node];
        int child = 2 * node + 1;
        while(child <= size){
            if(child < size && heap[child] < heap[child + 1]){
                child++;
            }

            if(x < heap[child]){
                heap[(child - 1) / 2] = heap[child];
                child = child * 2 + 1;
            }else{
                break;
            }
        }
        heap[(child - 1) / 2] = x;
    }

一樣就是給予一個樹根節點的 index 值就叫做 node，並且開始跟其子點之最大值比較，若有則調換，一樣也不需要真的有「調換的動作」，確認位置後再將值插入即可。
Adjust動作最多為從樹根移動到樹葉，因此時間也是 O(H) = O(logn)。

3. delete Max: O(logn)

    public int deleteMax(){
        int x = heap[0];
        heap[0] = heap[size--];
        adjust(0);
        return x;
    }

因為 heap[0] 一定是最大值，因此將值取出後，把最後一個節點移上 root，並做一次 Adjust 即可，因此時間複雜度跟 Adjust 相同。

4. find_Max: O(1)

    public int findMax(){
        return heap[0];
    }

直接return heap[0] 就是最大值樹根：O(1) 常數時間

5. build Heap: O(nlogn) or O(n)

我們昨天介紹的 top-down method 和 bottom-up method

    public Max_Heap(int[] arr, char method){

        this.heap = new int[1000];
        this.size = -1;

        if(method == 't'){
            for(int i = 0; i < arr.length; i++){
                insert(arr[i]);
            }
        }else if(method == 'b'){
            for(int i = 0; i < arr.length; i++){
                heap[++size] = arr[i];
            }
            int maxParent = (size - 1) / 2;
            for(int i = maxParent; i >= 0; i--){
                adjust(i);
            }
        }else{
            System.out.println("error");
        }
    }

6. merge two Heap: O(n)

基本上可以想成：把兩個 Array 合起來再做 botton-up 的 build_heap。因此時間為 O(2n) = O(n)

    public void mergeTwoHeap(Max_Heap h){
        for(int i = 0; i <= h.getSize(); i++){
            this.heap[++size] = h.heap[i];
        }

        int maxParent = (size - 1) / 2;

        for(int i = maxParent; i >= 0; i--){
            adjust(i);
        }
    }

完整的 heap class code

package CH5;

public class Max_Heap {
    private int[] heap;
    private int size;

    public int getSize(){
        return this.size;
    }
    public void setSize(int i){
        this.size = i;
    }
    public void printHeap(){
        System.out.print("Heap: ");
        for(int i = 0; i <= size; i++){
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public void insert(int x){
        heap[++size] = x;
        int child = size;
        int parent = (size - 1) / 2;

        while(parent >= 0){
            if(heap[parent] < x){
                heap[child] = heap[parent];
                child = parent;
                if(child == 0){
                    parent = -1;
                }else{
                    parent = (parent - 1) / 2;
                }
            }else{
                break;
            }
        }
        //System.out.printf("input %d into heap\n", x);
        heap[child] = x;
    }
    public void adjust(int node){
        int x = heap[node];
        int child = 2 * node + 1;
        while(child <= size){
            if(child < size && heap[child] < heap[child + 1]){
                child++;
            }

            if(x < heap[child]){
                heap[(child - 1) / 2] = heap[child];
                child = child * 2 + 1;
            }else{
                break;
            }
        }
        heap[(child - 1) / 2] = x;
    }

    public Max_Heap(int[] arr, char method){

        this.heap = new int[1000];
        this.size = -1;

        if(method == 't'){
            for(int i = 0; i < arr.length; i++){
                insert(arr[i]);
            }
        }else if(method == 'b'){
            for(int i = 0; i < arr.length; i++){
                heap[++size] = arr[i];
            }
            int maxParent = (size - 1) / 2;
            for(int i = maxParent; i >= 0; i--){
                adjust(i);
            }
        }else{
            System.out.println("error");
        }
    }

    public int deleteMax(){
        int x = heap[0];
        heap[0] = heap[size--];
        adjust(0);
        return x;
    }
    public int findMax(){
        return heap[0];
    }

    public void mergeTwoHeap(Max_Heap h){
        for(int i = 0; i <= h.getSize(); i++){
            this.heap[++size] = h.heap[i];
        }

        int maxParent = (size - 1) / 2;

        for(int i = maxParent; i >= 0; i--){
            adjust(i);
        }
    }
}

介紹完了 Priority Queue 最適合的結構 Heap，明天要來介紹 Double Ended Priority Queue。