在N个元素中选出最大的M个元素,出最大堆元素如果不是最大堆中最小值，应该有问题

Question

波波老师，这里有个特殊的case，一起讨论一下。
假设数组大小是5，最大堆大小为4，在前四个元素入堆后，第五个元素假设是最大的，此时入堆，如果没有将堆中最小的元素替换出来，则最终堆中的四个元素不是大小为5的数组中，最大的4个元素。
所以这里不能简单的将堆中最后一个元素删除，因为最后的叶子节点不一定是最大堆的最小值，这里就需要从M/2中选出最小值，然后删除。
所以当N远大于M时，算法概率上出问题是很低的。但是如果N和M相近，算法大概率会出问题的。

Answer 1

liuyubobobo 2020-04-18 01:55:32

算法没有问题。这不是一个概率算法，和概率一点儿关系都没有。

首先需要纠正的是，找 n 个元素的最大的 m 个元素，需要的是最小堆，不是最大堆。这个包含 m 个元素的最小堆中，保存着已知的最大的 m 个元素。堆顶是这最大的 m 个元素中的最小值。所以，如果新元素比堆顶元素大，也就是有了一个更大的元素出现，就把堆顶元素拿走，新元素入堆，维护了堆中是已知的最大的 m 个元素。

因此，你的叙述“这里不能简单的将堆中最后一个元素删除”也不对。我们不是将堆中最后一个元素删除，是将堆顶元素删除。

再仔细理解一下这个思路？

继续加油！：）

• 提问者 慕村1994116 #1

  谢谢波波老师，确实理解错误了，也很感谢你这么快速准确的回复。