堆（minHeapmaxHeap）的原理及其实现（java）

  堆（heap，特殊的完全二叉树）,为了实现优先队列（对队列中对最大或者最小M个元素进行跟踪）而产生。


满足条件
  使用minHeap作为例子，maxHeap类似。
  min：每个节点的值都小于/等于它的child；
  complete biTree:满足完全二叉树的特性。


Operation
insert
  1.将新的node插入叶子节点坐在层的最末端（维护complete biTree）；
  2.将该node和其parent node进行比较，如果不满足min的特性，交换两个节点的值；
  3.重复2过程直至满足条件。

remove
  1.将root的值用最末端的叶子节点代替，删除该叶子节点（维护complete biTree）；
  2.将root的值和其left和right child进行比较。如果不满足min的特性，将root和child中较小的值进行交换；
  3.重复2过程直至满足条件。


maxHeap
（很有趣的一个问题）对于数值型的maxHeap，如何使用现有的minHeap实现？
  在构建minHeap时，将所有的值取反。


底层实现
  利用heap完全二叉树的特性，使用数组按照BFS的顺序存放其值即可（一般在数组头部空置一个value，或者存节点的个数，方便计算）。

java代码

public class Heap<T extends Comparable> {
    /* 实现minHeap的两种operation：insert和remove；
     */
    private T[] heap;
    private int originSize; // 定义初始容量为10
    private int last;

    Heap() {
        originSize = 10;
        last = 1;
        this.heap = (T[]) new Comparable[originSize];
    }

    public void insert(T a) {
        this.heap[last] = a;
        int curNode = last;
        while (curNode / 2 > 0 && !checkUpMin(curNode)) {
            exchange(curNode, curNode / 2);
            curNode /= 2;
        }
        last += 1;
    }

    private boolean checkUpMin(int a) {
        /* 向上check节点a和它的parent是否满足min
         */
        int b = a / 2;
        return getCur(a).compareTo(this.heap[b]) >= 0;
    }

    private T getCur(int a) {
        /* 获取当前节点的值
         */
        return this.heap[a];
    }

    private T getLeft(int a) {
        /* 获取left child的值
         */
        int idx = a * 2;
        if (idx < last) {
            return getCur(idx);
        }
        return null;
    }

    private T getRight(int a) {
        /* 获取right child的值
         */
        int idx = a * 2 + 1;
        if (idx < last) {
            return getCur(idx);
        }
        return null;
    }

    private void exchange(int a, int b) {
        /* 交换两个节点a和b的值
         */
        T temp = getCur(a);
        this.heap[a] = getCur(b);
        this.heap[b] = temp;
    }

    public T removeMin() {
        T res = null;
        if (last <= 1) {
            return res;
        } else {
            res = this.heap[1];
            last -= 1;
            this.heap[1] = getCur(last);
            int curNode = 1;
            while (curNode < last && !checkDownMin(curNode)) {
                int minChild = getMinChild(curNode);
                exchange(curNode, minChild);
                curNode = minChild;
            }
        }
        return res;
    }

    private boolean checkDownMin(int a) {
        /* 向下check节点a和它的child是否满足min
         */
        int idx = getMinChild(a);
        if (idx == a) {
            return true;
        }
        return getCur(a).compareTo(getCur(idx)) <= 0;
    }

    private int getMinChild(int a) {
        /* 获取节点a和它的child中拥有最小值的节点索引
         */
        int res;
        if (isLeaf(a)) {
            res = a;
        } else if (onlyLeftExit(a)) {
            res = a * 2;
        } else if (onlyRightExit(a)) {
            res = a * 2 + 1;
        } else {
            res = a * 2;
            if (getLeft(a).compareTo(getRight(a)) > 0) {
                res += 1;
            }
        }
        return res;
    }

    private boolean isLeaf(int a) {
        /* 判断节点是否为叶子节点
         */
        return getLeft(a) == null && getRight(a) == null;
    }

    private boolean onlyLeftExit(int a) {
        /* 判断节点是否只有left child
         */
        return getLeft(a) != null && getRight(a) == null;
    }

    private boolean onlyRightExit(int a) {
        /* 判断节点是否只有right child
         */
        return getLeft(a) == null && getRight(a) != null;
    }

    public static void main(String[] args) {
        /* 测试inset和remove的功能是否正确
         */
        Heap<Integer> test = new Heap<>();
        test.insert(9);
        test.insert(5);
        test.insert(1);
        test.insert(4);
        test.insert(7);
        test.insert(3);
        for (int i = 0; i < 6; i++) {
            System.out.print(test.removeMin() + " "); // 应该按照1 3 4 5 7 9的顺序输出
        }
    }
}