topK 问题之为啥 TopK 用的是小根堆?

topK 问题最容易想到的两种解法，无非就是快排和堆。

• 快排用了分治是思想，根据一趟排序的下标来判断继续在哪边的区间里寻找
• topK 则是利用堆的性质，堆顶的元素一定是最大(大根堆)或最小(小根)

今天这篇文章主要是说明一下在堆的解法中：

为啥求最大 TopK 要用小根堆？

假如求Top10，我们就维护一个堆。堆顶最小。

如果堆实现了 Top() 方法(获取堆顶的值)

则解法如下：

1
2
3
4
5
6
7

if Len() < 10
	Push //不足 10 就入堆
else
	if x < Top()
		continue // x 比现在 10 个里最小的还小，x 肯定不可能是答案，扔掉
	else
		Push

最后堆里 10 个元素就是答案。

堆没有 Top 方法

在 go 的 heap 包里，接口没有定义 Top 方法，这时候我们只能用一个降级方案：

1
2
3

Push
if Len() > 10
	Pop()

每次都 Push 进去，如果堆长度超过 10，则堆顶的一定不是答案。需要 Pop。

这个方案会比上面的多出 Push 的成本和 Pop 的成本。

为啥不直接用大根堆呢？

既然求最大的 10 个数，为啥不直接大根堆，这样最后留下来的 10 个不就是答案吗？

并不是的。

假设堆里已经有 10 个元素。我们知道最大的在堆顶。

当第 11 个入堆时。假如它非常大，需要代替堆顶位置。

那么，尴尬的问题就出现了：

– 现有的 10 个元素，谁出列呢？

– 肯定是最小的出列啊！

炫杉：靠，我是大顶堆，我只管顶上的最大。我可不知道底下那个最小啊！

– 好吧，你不用说了，最小的出列，那，那不就得用小根堆么！

炫杉：那你应该懂了。

License

Adopting CC BY-NC-SA 4.0 License Agreement

Share