使用堆选出前100个元素

Question

怎么是用最小堆呢，是按从大到小排列的前100么？

如果是从小到大的话，如果用最小堆，那么应该存在两种情况：一、新添加的元素比堆顶元素还要大，这时候不应该移除堆顶元素，因为按从小到大它应该是排在新添加元素的前面，但是它有可能比堆中的其它一些元素小啊，它不是应该只可能挤掉最大的那个么，所以不是应该使用最大堆么？二、新添加的元素比堆顶元素要小，虽然堆顶元素排在新元素后面，但它比堆中其它任何元素都小啊，不也是应该挤掉最大元素么？

Answer 1

liuyubobobo 2017-06-10 00:46:32

如果要找到前100大元素，我们需要维护一个最小堆。最小堆是指保持着堆顶元素是这个堆中所有元素里最小的那个元素这样的性质。但是这个最小堆里存储的是已经见过的最大的100个元素。

当有一个新的元素来到的时候，如果这个新元素比最小堆堆顶元素还要大，则将最小堆堆顶元素移除，同时将这个新元素放进堆里；

如过这个元素比最小堆堆顶元素还要小，直接将这个元素扔掉即可。

• 提问者 易萧 #1

  非常感谢！