@@ -0,0 +1,2592 @@
+package cn.webank.ctrl.learn.lecture.lecture.list;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * @author ctrlzhang on 2018/5/16.%0A */%0Apublic class Heap %7B%0A    public List%3CInteger%3E arr = new ArrayList%3C%3E();%0A    private int capacity = 0;%0A%0A    Heap(List%3CInteger%3E input) %7B%0A        this.arr = input;%0A        this.capacity = input.size();%0A    %7D%0A%0A    public void heapfy() %7B%0A        int n = arr.size();%0A        for(int i = (n - 1) / 2; i %3E= 0; i--) %7B%0A            adjust(i);%0A        %7D%0A    %7D%0A%0A    public void adjust(int idx) %7B%0A        int left = idx * 2 + 1;%0A        int right = idx * 2 + 2;%0A        int end = capacity - 1;%0A        int tmp = idx;%0A        if (left %3C end) %7B%0A            if (arr.get(tmp) %3E arr.get(left)) %7B%0A                tmp = left;%0A            %7D%0A        %7D%0A%0A        if (right %3C end) %7B%0A            if (arr.get(tmp) %3E arr.get(right)) %7B%0A                tmp = right;%0A            %7D%0A        %7D%0A%0A        if (tmp != idx) %7B%0A            swap(arr, tmp, idx);%0A            adjust(tmp);%0A        %7D%0A    %7D%0A%0A    public int pop() %7B%0A        if (capacity %3C= 0) return -1;%0A        int ans = arr.get(0);%0A        swap(arr, 0, capacity - 1);%0A        arr.remove(capacity - 1);%0A        capacity--;%0A        adjust(0);%0A        return ans;%0A    %7D%0A%0A    public void push(int d) %7B%0A        arr.add(d);%0A        capacity = arr.size();%0A        int idx = capacity - 1;%0A        int parent = (idx - 1) / 2;%0A        while (parent %3E= 0) %7B%0A            if (arr.get(idx) %3C arr.get(parent)) %7B%0A                swap(arr, idx, parent);%0A                idx = parent;%0A                parent = (idx - 1) / 2;%0A            %7D else %7B%0A                break;%0A            %7D%0A        %7D%0A    %7D%0A%0A    void swap(List%3CInteger%3E data, int l, int r) %7B%0A        int tmp = data.get(l);%0A        data.set(l, data.get(r));%0A        data.set(r, tmp);%0A    %7D%0A%0A    void output() %7B%0A        for (int i = 0; i %3C arr.size(); i++) %7B%0A            System.out.println(this.arr.get(i));%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        List%3CInteger%3E input = new ArrayList%3C%3E();%0A        input.add(10);%0A        input.add(5);%0A        input.add(25);%0A        input.add(3);%0A        input.add(99);%0A%0A        Heap myHeap = new Heap(input);%0A        myHeap.heapfy();%0A        myHeap.output();%0A%0A        System.out.println(%22==========%22);%0A%0A        myHeap.push(1);%0A        myHeap.output();%0A        System.out.println(%22==========%22);%0A%0A        int k = 0;%0A        while (k %3C 3) %7B%0A            int val = myHeap.pop();%0A            System.out.println(%22pos ans=%22 + val);%0A            k++;%0A        %7D%0A        System.out.println(%22==========%22);%0A        myHeap.output();%0A    %7D%0A%7D%0A

Create heap.java