11.Hedp(堆)

概念：

堆(Heap)亦被称为：优先队列(priority queue)
Binary Heap is a common type of Heap.
性质：堆的实现通过构造二叉堆(binary heap),这种数据结构具有以下性质
1.任意节点小于等于它的所有后裔，最小元素在堆的根上(堆序性)。
2.堆总是一棵完全树。complete tree,在node数量相同的情况下，完全树高度最小height肯定是lgn，traversal或其他操作复杂度更低，普通的二叉树则没有这种优势。
3.将根节点最大的堆叫做MAX HEAP, 根节点最小的堆叫做最小堆MIN HEAP
4.index of IChild = index of parent * 2+1
5.index of rChild = index of parent * 2+2
(第4第5的特性决定了二叉堆可以将所有的node放到一个数组中可以快速地找到某个node的子node)
6.unsorted but follow rules above

java PriorityQueue支持的基本操作

        Queue<Integer> pq = new PriorityQueue<>();
        pq.offer(6);
        pq.offer(5);
        pq.offer(4);//复杂度O(lgn) 插入到heap的最后一个index，再跟parent节点比较，比parent小就往上冒泡

        System.out.println(pq.peek());//4 O(1)
        System.out.println(pq.poll());//4
        System.out.println(pq.poll());//5
        //pq.poll() 复杂度O(lgn) 删除第一个index，再将最后一个元素移到顶部，再往下压与较小的子节点交换，直到没有比它小的节点

练习

`1.find smallest k elements from an unsorted array of size n
solution1: maintain a MAX-Heap of size k