Java集合总结（三）：堆与优先级队列

堆

满二叉树：满二叉树是指，除了最后一层外，每个节点都有两个孩子，而最后一层都是叶子节点，都没有孩子。

完全二叉树：完全二叉树不要求最后一层是满的，但如果不满，则要求所有节点必须集中在最左边，从左到右是连续的，中间不能有空的。

一个特性：给定任意一个节点，可以根据其编号直接快速计算出其父节点和孩子节点编号，如果编号为i，则父节点编号即为i/2，左孩子编号即为2*i,右孩子编号即为2*i+1。比如，对于5号节点，父节点为5/2即2，左孩子为2*5即10，右孩子为2*5+1即11。

上述特性使得逻辑概念上的二叉树可以方便的存储到数组中，数组中的元素索引就对应节点的编号，树中的父子关系通过其索引关系隐含维持，不需要单独保持。

排序二叉树：排序二叉树是完全有序的，每个节点都有确定的前驱和后继，而且不能有重复元素。

堆：逻辑概念上是一颗完全二叉树，而物理存储上使用数组。与排序二叉树不同，在堆中，可以有重复元素，元素间不是完全有序的，但对于父子节点之间，有一定的顺序要求，根据顺序分为两种堆：

- 最大堆：每个节点都不大于其父节点。这样，对每个父节点，一定不小于其所有孩子节点，而根节点就是所有节点中最大的，对每个子树，子树的根也是子树所有节点中最大的。
- 最小堆：与最大堆正好相反，每个节点都不小于其父节点。这样，对每个父节点，一定不大于其所有孩子节点，而根节点就是所有节点中最小的，对每个子树，子树的根也是子树所有节点中最小的。

PriorityQueue
优先级队列，内部使用堆实现，非完全排序但输出有序。

使用数组作为堆的存储，默认数组大小为11，可以手动指定初始化大小，扩容策略是每次增加到原来的1.5倍。

元素要么实现comparable接口要么传入一个比较器comparator。
实现了Queue接口，有优先级，内部是用堆实现的，这决定了它有如下特点：

可以看做是一种比较通用的实现了堆的性质的数据结构，可以用PriorityQueue来解决适合用堆解决的问题

PriorityQueue应用：
1、前K个最大元素：
　　维护一个长度为k的数组，用最小堆实现，每来一个和堆顶的值作比较，小于等于则舍弃，大于则替换原来的堆顶，然后调整堆；

2、求中值（不断入队，故排序不可用）：

巴特西