数据结构-堆

插入：每次插入的时候，都往最后一个插入，然后使它上浮。

弹出根节点：让根节点元素和尾节点进行交换，然后让现在的根元素下沉

可以用来做堆排序。大顶堆、小顶堆。

public class minHeap {
    private LinkedList<Integer> list;

    public minHeap() {
        list = new LinkedList<>();
        list.add(Integer.MIN_VALUE);
    }

    public void push(int a) {
        list.add(a);
        FloatIterate(list.size() - 1);
    }

    public int pop() {
        int n = 1;
        assert (n > 0 && n < list.size());
        int ret = list.get(n);
        Collections.swap(list, 1, list.size() - 1);
        list.removeLast();
        DownRecursion(1);
        return ret;
    }

    private void DownRecursion(int n) {
        if (n * 2 > list.size() - 1) {
            return;
        }
        int child;
        if (list.size() - 1 == n * 2) child = n * 2;
        else child = list.get(n * 2) > list.get(n * 2 + 1) ? n * 2 + 1 : n * 2;
        if (list.get(child) < list.get(n))
            Collections.swap(list, n, child);
        DownRecursion(child);
    }

    public int size() {
        return list.size() - 1;
    }

    public static void main(String[] args) {
        minHeap mh = new minHeap();
        int[] a = new int[]{2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
        for (int i = 0; i < 10; i++) {
            mh.push(a[i]);
        }

        while (mh.size() > 0) {
            System.out.printf("%d ", mh.pop());
        }
    }

    private void FloatRecursion(int n) {
        int fatherPos = n / 2;
        if (fatherPos == 0) return;
        if (list.get(fatherPos) > list.get(n)) {
            Collections.swap(list, fatherPos, n);
            FloatRecursion(fatherPos);
        }
    }

    private void FloatIterate(int n) {
        int fatherPos = n / 2;
        while (fatherPos != 0 && (list.get(fatherPos) > list.get(n))) {
            Collections.swap(list, fatherPos, n);
            n = fatherPos;
            fatherPos /= 2;
        }
    }
}