相关疑难解决方法(0)

相关问题:

• 具有固定大小的Java PriorityQueue
• 我如何使用PriorityQueue？
• 获取数组中n个最小元素的索引
• Scala:有没有像我在Java中那样使用PriorityQueue的方法？

我有一个非常大的数据集(超过500万件),我需要从中获得N个最大的项目.最自然的方法是使用堆/优先级队列,只存储前N个项目.JVM(Scala/Java)的优先级队列有几个很好的实现,即:

• scala.collection.mutable.PriorityQueue
• java.util.PriorityQueue中
• lucene.util.PriorityQueue

前2个很好,但它们存储了所有项目,在我的情况下会产生关键的内存开销.第三个(Lucene实现)没有这样的缺点,但正如我从文档中看到的那样,它也不支持自定义比较器,这对我来说没用.

所以,我的问题是:是否有PriorityQueue实现与固定容量和自定义比较？

UPD.最后,根据Peter的回答,我创建了自己的实现:

public class FixedSizePriorityQueue<E> extends TreeSet<E> {

    private int elementsLeft;

    public FixedSizePriorityQueue(int maxSize) {
        super(new NaturalComparator());
        this.elementsLeft = maxSize;
    }

    public FixedSizePriorityQueue(int maxSize, Comparator<E> comparator) {
        super(comparator);
        this.elementsLeft = maxSize;
    }


    /**
     * @return true if element was added, false otherwise
     * */
    @Override
    public boolean add(E e) {
        if (elementsLeft == 0 && …

鉴于以下问题:

"从数字流中存储最大的5000个数字"

我们想到的解决方案是二进制搜索树,它保持树中节点数量的计数,以及一旦计数达到5000就对最小节点的引用.当计数达到5000时,可以将每个要添加的新数字进行比较树中最小的项目.如果更大,则可以添加新数字,然后移除最小的数字并计算新的最小数量(这应该非常简单,已经具有前一个最小值).

我对这个解决方案的关注是二叉树自然会出现偏差(因为我只是在一边删除).

有没有办法解决这个问题,不会造成一个非常歪斜的树？

如果有人想要它,我已经为我的解决方案包括伪代码到目前为止:

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) …