23

也许我没有使用正确的数据结构。我需要使用一个集合，但也想有效地返回第 k 个最小的元素。TreeSetJava可以做到这一点吗？似乎没有内置的方法TreeSet可以做到这一点。

4

8 回答 8

23

我不相信TreeSet有直接做到这一点的方法。有支持 O(log n) 随机访问的二叉搜索树（它们有时称为顺序统计树），并且有可用的这种数据结构的 Java 实现。这些结构通常实现为二进制搜索树，在每个节点中存储信息，计算节点左侧或右侧有多少元素，因此可以向下搜索树以通过下降到适当的子树来找到适当的元素每一步。Cormen、Rivest、Leisserson 和 Stein 的经典“算法简介，第三版”一书在他们的“增强数据结构”一章中探讨了这种数据结构，如果您对如何自己实现一个数据结构感到好奇。

或者，您可以（在某些情况下）使用TreeSet'tailSet方法和修改后的二进制搜索来尝试查找第 k 个元素。具体来说，查看 的第一个和最后一个元素TreeSet，然后（如果可能的话，给定内容）选择介于两者之间的一些元素并将其作为参数传递给以tailSet获取中点之后集合元素的视图。使用 中的元素数量tailSet，您可以决定是否找到了该元素，或者是探索树的左半部分还是右半部分。这是对树的稍微修改的插值搜索，可能会很快。但是，我不知道内部复杂性tailSet方法，所以这实际上可能比顺序统计树更糟糕。如果您无法计算两个元素的“中点”，它也可能会失败，例如，如果您将Strings 存储在TreeSet.

于 2012-01-13T20:33:16.200 回答
18

您只需要迭代到元素k。一种方法是使用Guava的Iterables.get方法之一：

T element = Iterables.get(set, k);

没有内置方法可以做到这一点，因为 aSet不是 aList并且像这样的基于索引的操作通常是为Lists 保留的。ATreeSet更适合于查找最近包含的 >= 某个值的元素。

如果对第 k 个最小元素的最快访问非常重要，您可以做的一件事是使用 anArrayList而不是 aTreeSet并通过二进制搜索插入点并在该索引处插入元素或替换现有元素来处理插入该索引，取决于搜索的结果。然后你可以通过调用来获得 O(1) 中的第 k 个最小元素get(k)。

如果您真的需要，您甚至可以创建一个SortedSet处理所有这些的实现并添加该方法。get(index)

于 2012-01-13T20:32:58.917 回答
10

使用TreeSet.iterator()以升序获取迭代器并调用next()K 次：

// Example for Integers
Iterator<Integer> it = treeSet.iterator();
int i = 0;
Integer current = null;
while(it.hasNext() && i < k) {
   current = it.next();
   i++;
}
于 2012-01-13T20:31:40.837 回答
8

https://github.com/geniot/indexed-tree-map

我有同样的问题。所以我拿了 java.util.TreeMap 的源代码并写了IndexedTreeMap。它实现了我自己的IndexedNavigableMap：

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

该实现基于在更改红黑树时更新节点权重。权重是给定节点下的子节点数加一 - self。例如，当一棵树向左旋转时：

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight 只是将权重更新到根：

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

当我们需要通过索引找到元素时，这里是使用权重的实现：

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

查找键的索引也非常方便：

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    if (e.left != null) {
        index += getWeight(e.left);
    }
    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

您可以在https://github.com/geniot/indexed-tree-map找到这项工作的结果。

于 2013-02-10T22:17:15.367 回答
3 
TreeSet<Integer> a=new TreeSet<>();
a.add(1);
a.add(2);
a.add(-1);

System.out.println(a.toArray()[0]);

这可能会有所帮助

于 2019-09-05T17:06:41.500 回答
1

[以下，我将“第k个最小元素搜索操作”缩写为“第K个操作”]

您需要提供更多详细信息。您的数据结构将提供哪些操作？与N相比，第K次操作中的K非常小，还是可以是任何东西？与查找相比，您多久进行一次插入和删除？与查找相比，您多久进行一次第 K 个最小元素搜索？您是在 Java 库中寻找几行代码的快速解决方案，还是愿意花费一些精力来构建自定义数据结构？

要提供的操作可以是以下任何子集：

  • LookUp（通过键查找元素；其中键是可比较的并且可以是任何东西）

  • 插入

  • 删除

  • 第K个

以下是一些可能性：

  • 如果没有/很少插入和删除，您可以对元素进行排序并使用数组，查找时间为O(Log(N))，对于Kth查找时间为O(1)。

  • 如果LookUp的O(Log(N))，Insert，Delete和Kth op的O(k)。足够好，可能最简单的实现是跳过列表。（如果您需要更多详细信息，维基百科的文章非常好）

  • 如果K足够小，或者Kth操作只会在“插入和删除阶段”之后进行，您可以将最小的K个元素保留在堆中，在插入和删除O(N + k Log k)时间之后进行排序。（您还需要一个单独的 Hash 用于LookUp）

  • 如果K是任意的并且O(N)对第 K次操作足够好，则可以使用 Hash 进行O(1)时间查找，并使用“单边快速排序”算法进行第 K次操作（基本思想是做一个快速排序，但在每个二进制除法上仅在您真正需要的一侧递归；这将给出（这是一个粗略的简化）N (1/2 + 1/4 + 1/8 + ... ) = O(N)预期时间）

  • 您可以构建一个增强的“简单”间隔树结构，每个节点都保持其子节点的数量，因此只要树是平衡的， LookUp、Insert、Delete、Kth都在O(Log N)时间内计算，但也许它会如果您是新手，实施起来并不难。

等等等等。作为您问题的可能解释，备选方案的集合是无限的。

于 2012-01-14T01:40:15.413 回答
0

您可以使用 ConcurrentSkipListSet 并使用 toArray() 方法吗？ConcurrentSkipListSet 按元素的自然顺序排序。我唯一不确定的是 toArray() 是否为 O(n)，或者因为它由 List 支持（由数组支持，如 ArrayList），所以它是 O(1)。

如果 toArray() 是 O(1) 你应该能够成为一个 skipList.toArray()[k] 来获得第 k 个最小的元素。

于 2012-01-14T16:18:10.040 回答
-1

我知道这个问题已经很老了，但是由于 TreeSet 实现了 NavigableSet 您可以访问在恒定时间内运行的 subSet 方法。

subSet(k, k + 1).first();

first() 调用需要 log(n) 时间，其中 n 是原始集合的大小。这确实会创建一些不必要的对象，这些对象可以通过更健壮的 TreeSet 实现来避免，但它避免了使用第三方库。

于 2013-05-30T17:10:15.840 回答