收集一些元素,从N个元素中找到M个最大或最小元素
优先队列 MAXPQ
- 两个重要操作： 删除最大元素
delMax()和插入元素insert
二叉堆实现优先级队列
- 二叉堆的每个元素要大于两个特定位置的元素
- k 的上一层是 k/2, k 的下一层是 2k、2k+1 (a[0] 作为哨兵节点可以简化这个的实现)
- 两个帮助方法，上浮
swim(int k),下沉sink(int k)- 上浮实现： while 反复比较 k 和 k/2 的大小
- 下沉实现： while 反复比较 k 和 2k 的关系，注意要比较 2k 和 2k + 1 的大小，总是选择较大的，因为 k 要比 2k 和 2k + 1 都大
- delMax 的实现 -> 先交换最后一个值和Max,删除 Max,然后下沉
- insert 的实现 -> 先把数插入最后一个位置，然后上浮