概念:
堆(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