数据结构堆和优先队列

java中优先队列：import java.util.PriorityQueue

2、优先队列时间复杂度

3、二叉堆（Binary Heap）

4、二叉堆是一颗完全二叉树

5、二叉堆的性质

6、用数组存储二叉堆

7、向堆中添加元素和Sift Up（上浮）

在最后添加一个元素，跟父亲节点进行比较，如果大于父亲节点的值，则互换位置。

8、取出堆中的最大元素和Sift Down（下沉）

取出root，然后将最后一个节点放到root位置，然后跟左右叶子节点值比较，跟位置大的节点互换位置，称为Sift Down。

9、堆的时间复杂度分析

add和extractMax时间复杂度都是O(logn)

10、replace

replace：取出最大元素，放入一个新元素；

实现：可以先extractMax，在add，再次O(logn)的操作；

实现：可以直接将堆顶元素替换以后Sift Down，一次O(logn)的操作

11、heapify（堆化）

heapify：将任意数组整理成堆的形状

12、其他堆

d叉堆 d-ary heap：二个叉的堆是二叉堆，d个叉的堆就是d叉堆；

索引堆

二项堆

斐波那契堆

13、广义队列

普通队列，优先队列

栈，也可以理解成是一个队列

14、有点队列经典问题

在1,000,000个元素中选出前100名？（在N个元素中选出前M个元素）

排序算法：NlogN

使用优先队列：NlogM

优先队列思路：维护当前看到的前M个元素（使用最小堆）。遍历N个元素，跟最后一个元素比，如果比最后一个元素小就add或replace，

插入元素始终保持是最小堆。