是否有一种数据结构能够获取 N 个最大元素的集合，并在 Java 中实现？

Question

java 中有 TreeSet 数据结构，它提供了获取 1 个最大元素的能力。我需要允许收集 N 个最大元素的数据结构。

我需要这样的东西:

GreatestN<Integer> greatest = new GreatestN<>(Arrays.asList(5, 2, 1, 7));
greatest.getN(2); // returns {1, 2}
greatest.getN(3); // returns {1, 2, 5}

greatest.add(0);
greatest.getN(2); // returns {0, 1}

Answer 1

您可以对您的列表进行排序，然后传递索引值以获得最大的数字。

    List<Integer> greatest = Arrays.asList(5, 2, 1, 7);
    Collections.sort(greatest); // By default sorts ascending 
    System.out.println(greatest.get(greatest.size()-1)); //will give you greatest element in the list.
    //System.out.println(greatest.get(greatest.size()-1-nthNumber));
    System.out.println(greatest.get(0));//will give you lowest element in the list.

Answer 2

TreeSet 具有基于元素值（headSet 和 tailSet）而不是索引获取子集的方法。对于基于索引的方法，您需要使用 List 和 subList().

List<Integer> list = Arrays.asList(5, 2, 1, 7);
list.sort();
List<Integer> topFive = list.subList(0, 5);

Answer 3

我无法在网上找到解决您的问题的方法，所以我写了一个。

如果您只想使用您提供的代码而不修改它，请将我的代码作为 class 添加到您的项目中。

public class GreatestN <T extends Comparable<T>>{


    private List<T> list;

    public GreatestN(List newList){

        this.list = newList;

        Collections.sort(list);

    }

    public List getN(int numbers){

        List<T> returnList = new ArrayList();

        if(numbers>list.size()){
            numbers = list.size();
        }

        for(int i = 0; i < numbers; i++){

            returnList.add(this.list.get(i));

        }

        return returnList;
    }

    public void add(T t){

        list.add(0,t);

        Collections.sort(list);

    }

}

Answer 4

感谢所有的回答和评论，尤其是 shmosel 的回答和评论：

You can get a descending iterator from a TreeSet.

看起来我要问的结构不存在，但它可以很简单地创建：

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

    public ArrayList<E> getFirstN(int n) {
        if (n > this.size()) {
            n = this.size();
        }

        ArrayList<E> firstN = new ArrayList<>(n);
        Iterator iter = this.iterator();

        for (int i = 0; i < n; i++) {
            firstN.add((E) iter.next());
        }

        return firstN;
    }
}

是否有一种数据结构能够获取 N 个最大元素的集合，并在 Java 中实现？

Is there a data structure that has ability to get collection of N greatest elements, implemented in Java?

java

data-structures

treeset