从一串数字中存储最大的5000个号码

鉴于以下问题：

“从一串数字中存储最大的5000个号码”

想到的解决scheme是一个二叉search树，一旦计数达到5000，就保持树中节点数量的计数和最小节点的引用。当计数达到5000时，每个要添加的新数字可以与树中最小的项目。 如果更大，可以添加新的数字，然后删除最小的和新的最小的计算（这应该是非常简单的，已经有以前最小）。

我对这个解决scheme的担心是二叉树自然会偏斜（因为我只是在一边删除）。

有没有办法解决这个问题，不会造成一个可怕的歪斜的树？

如果有人愿意，我已经在下面列出了我的解决scheme的伪代码：

process(number) { if (count == 5000 && number > smallest.Value) { addNode( root, number) smallest = deleteNodeAndGetNewSmallest ( root, smallest) } } deleteNodeAndGetNewSmallest( lastSmallest) { if ( lastSmallest has parent) { if ( lastSmallest has right child) { smallest = getMin(lastSmallest.right) lastSmallest.parent.right = lastSmallest.right } else { smallest = lastSmallest.parent } } else { smallest = getMin(lastSmallest.right) root = lastSmallest.right } count-- return smallest } getMin( node) { if (node has left) return getMin(node.left) else return node } add(number) { //standard implementation of add for BST count++ } 

Answer 1

最简单的解决scheme是维持最大容量为5000的最小堆 。

• 每当新号码到达时，检查堆是否小于5000，如果是 – 添加。
• 如果不是，请检查最小值是否小于新元素，如果是，则popup并插入新元素。
• 当你完成了 – 你有一个包含5000个最大元素的堆。

这个解决scheme是O(nlogk)复杂性，其中n是元素的数量， k是你需要的元素的数量（在你的情况下是5000）。

在O(n)也可以使用selectalgorithm完成 – 存储所有元素，然后find第5001个最大元素，并返回比它大的一切。 但是实施起来比较困难，而且投入的规模也不大 – 可能不会更好。 另外，如果stream包含重复项，则需要更多的处理。

Answer 2

使用（最小）优先级队列。 将每个传入项目添加到队列中，当大小达到5,000时，每次添加传入元素时都要删除最小（顶部）元素。 队列将包含5000个最大的元素，当input停止时，只需删除内容。 这MinPQ也被称为堆，但这是一个超载的术语。 插入和删除大约需要log2（N）。 如果N最大值为5000，那么这个值就是正在处理的项目数量的12倍[log2（4096）= 12]倍。

一个很好的信息来源是Robert Sedgewick和Kevin Wayne的algorithm（第四版）。 coursera.org上有一个很棒的MOOC，它基于这个文本。