优先队列

大概在2012年学习堆（优先队列）及其排序。
现在想实现一个最小堆，连定义都不清楚了。
1.完全二叉树，所以插入一个节点，只能按照顺序来。
2.节点最大（小）性：每个节点的元素必须大于（小于）孩子节点的元素。

用途：topK问题，如果K是最大的K个数，那么使用最小堆；如果K是最小的K个数，使用最大堆，时间复杂度是O(NlogK)。另外说一下，使用快速排序的思想也可以实现，事件复杂度也是O(NlogK)。

public class MinHeap<E extends Comparable> {

    private List<E> heap;

    public MinHeap(E[] items) {
        heap = new ArrayList<>();
        for (E item : items) {
            add(item);
        }
    }
    // 入队
    public void add(E item) {
        heap.add(item);
        int i = heap.size() - 1;
        while (i != 0) {
            int j = (i - 1) >> 1;
            if (heap.get(i).compareTo(heap.get(j)) < 0) {
                E e = heap.get(i);
                heap.set(i, heap.get(j));
                heap.set(j, e);
                i = j;
            } else {
                break;
            }
        }
    }
   // 出队
    public E remove() {
        int size = heap.size();
        if (size == 0) {
            return null;
        }
        E top = heap.get(0);
        E last = heap.get(size - 1);
        heap.set(0, last);
        heap.remove(size - 1);
        size = heap.size();
        int i = 0;
        while (i < size) {
            int x = (i << 1) + 1;
            int y = x + 1;
            if (x >= size) {
                break;
            }
            int j;
            if (y >= size || heap.get(x).compareTo(heap.get(y)) < 0) {
                j = x;
            } else {
                j = y;
            }
            if (heap.get(i).compareTo(heap.get(j)) > 0) {
                E e = heap.get(i);
                heap.set(i, heap.get(j));
                heap.set(j, e);
            } else {
                break;
            }
            i = j;
        }
        return top;
    }

    @Override
    public String toString() {
        return "MinHeap{" +
                "heap=" + heap +
                '}';
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[12];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ThreadLocalRandom.current().nextInt(arr.length << 1);
        }
        MinHeap<Integer> minHeap = new MinHeap<>(arr);
        System.out.println(minHeap);
        Integer integer;
        while ((integer = minHeap.remove()) != null) {
            System.out.print(integer + "\t");
        }
        System.out.println("======");
    }

}

参考：数据结构-堆的实现