如何找出一个数列中的最大的N个值?
这是一个在面试中经常遇见的问题,此问题的关键是应尽可能的减少节点的比较次数,从而降低时间复杂度.因此选择小顶堆这个数据结构.
那么小顶堆是什么样的数据结构,又为什么能降低时间复杂度呢?
小顶堆是二叉树结构,但其存储结构是数组.
如果对小顶堆的定义以及父子节点在数组中的关系还不了解,建议先阅读文章二叉树.
下面通过一个例子来看一下小顶堆是如何添加和删除节点的.
array=[42, 41, 31, 7, 17, 2]
一. 添加节点
节点添加时,首先将要加入的节点放入树的最后一个节点上(数组的末尾),再将节点与自己的父节点比较,如果比父节点小,则交换位置,按此逻辑递归处理,一直遇到比父节点值大的情况或者已经换到了小顶堆的根节点位置.
1. 节点42,空树,直接放入根节点.对应数组放入首位.
2. 节点41,先放入树的最后节点上,即节点42的左叶子节点上,并与父节点(节点42)比较,比父节点值小,交换位置.
3. 节点31,放入树最后节点,并与父节点41比较,比父节点值小,交换位置.
4. 节点7,首先放在树最末节点,比父节点42值小,交换位置.在与当前节点位置的父节点31比较,仍小于父节点,再次交换位置.
5. 其他节点的添加过程,不再赘述了,我们看下最后结果.可以发现小顶堆对应的数组并不是有序递增的,这也是小顶堆的特点之一.
二. 删除节点
小顶堆的删除过程,主要是指删除数组的最小节点,也就是array[0],但通过数据节点交换,是不需要对各元素移位或进行数组复制的.
这也是在TopN问题中,能始终保持N个元素,并且很高效的一个原因.
删除最小节点过程是用树的最后一个节点替换为根节点,并重新调整为小顶堆.
在调整的过程中是将父节点与叶子节点中较小的节点交换,并递归处理,直到遇到较大节点或到了最底层叶子节点.
按上图树结构,观察下节点移除过程.
array=[2,17,7,42,31,41]
1. 删除根节点2
将节点41替换为根节点,并找到较小的叶子节点7,交换位置.
2. 删除根节点7
将原有最后一个节点代替为根节点,并与自己较小的叶子节点(17)比较,并交换位置.再次与自己当前位置的叶子节点(42)比较,小于叶子节点值,不需要再次交换.
3.其他节点的删除过程也类似这样,不在赘述了.
在节点的添加和删除过程中,并不需要遍历数组中的所有元素,就能找到自己合适的位置,比较次数也明显少了很多.
在java中,解决TopN问题,可以直接使用优先队列类(PriorityBlockingQueue),这个类已经替我们实现了添加和删除操作,并且能通过扩展Comparator能自定义排序方法.有兴趣的可以看看源码,方法的实现过程也与上述过程一致,非常好理解.
添加节点方法:
siftUpComparable()
siftUpUsingComparator()
删除节点方法:
siftDownComparable()
siftDownUsingComparator()
我们通过TopN问题,发现小顶堆是最优解,并详细了解了节点的添加和删除过程.最后附上Java版的小顶堆(优先队列)如何解决TopN问题的.
附上代码:
代码语言：javascript复制 static void topN(int[] data, int N) {
PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
int minData = data[0];
for (int i = 0; i < data.length; i ) {
if (queue.size() == N) {
if (minData < data[i]) {
// 大于原来最小的，就放进去新的,删除旧的
queue.offer(data[i]);
int header = queue.poll();
minData = header;
}
} else {
// 最开始 N个，直接保留
minData = Math.min(minData, data[i]);
queue.offer(data[i]);
}
}
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
