Cách trả về phần tử k trong TreeSet trong Java

Question

Có lẽ tôi không sử dụng đúng cấu trúc dữ liệu. Tôi cần phải sử dụng một bộ, nhưng cũng muốn trả lại hiệu quả phần tử nhỏ nhất thứ k. TreeSet có thể làm được điều này không? Có vẻ như không có phương pháp TreeSet tích hợp để làm điều này.

Hãy giúp tôi.

Answer 1

Sử dụng TreeSet.iterator() để có được một iterator thứ tự tăng dần và gọi next() K lần:

// Example for Integers 
Iterator<Integer> it = treeSet.iterator(); 
int i = 0; 
Integer current = null; 
while(it.hasNext() && i < k) { 
    current = it.next(); 
    i++; 
} 

Answer 2

Bạn chỉ cần lặp để yếu tố k. Một cách để làm điều đó sẽ được sử dụng một trong Iterables.get phương pháp Guava 's:

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

Không có được xây dựng trong phương pháp để làm điều này vì một Set không phải là một List và chỉ số dựa trên hoạt động như thế nói chung là các Ltd. cho List s. A TreeSet phù hợp hơn với những thứ như tìm phần tử có chứa gần nhất> = một số giá trị.

Một điều bạn thể làm gì nếu việc tiếp cận nhanh nhất có thể để các phần tử nhỏ nhất thứ k là thực sự quan trọng sẽ được sử dụng một ArrayList chứ không phải là một TreeSet và xử lý chèn bởi tìm kiếm nhị phân cho điểm chèn và một trong hai cách chèn các phần tử ở chỉ mục đó hoặc thay thế phần tử hiện có tại chỉ mục đó, tùy thuộc vào kết quả tìm kiếm. Sau đó, bạn có thể nhận được phần tử nhỏ nhất thứ k trong O (1) bằng cách chỉ cần gọi get(k).

Bạn thậm chí có thể tạo triển khai SortedSet xử lý tất cả điều đó và thêm phương thức get(index) nếu bạn thực sự muốn.

Answer 3

Tôi không tin rằng TreeSet có phương thức trực tiếp thực hiện việc này. Có cây tìm kiếm nhị phân hỗ trợ truy cập ngẫu nhiên O (log n) (đôi khi chúng được gọi là số liệu thống kê đơn hàng cây) và có sẵn Java implementations of this data structure. Các cấu trúc này thường được thực hiện dưới dạng cây tìm kiếm nhị phân lưu trữ thông tin trong mỗi nút đếm số lượng phần tử ở bên trái hoặc bên phải của nút, do đó tìm kiếm cây có thể được thực hiện để tìm phần tử thích hợp bằng cách giảm dần vào cây con phù hợp tại từng bước. Cuốn sách "Giới thiệu về thuật toán, ấn bản thứ ba" cổ điển của Cormen, Rivest, Leisserson và Stein khám phá cấu trúc dữ liệu này trong chương "Augmenting Data Structures" nếu bạn tò mò làm thế nào để tự mình thực hiện.

Ngoài ra, bạn có thể (trong một số trường hợp) sử dụng phương thức TreeSet của tailSet và tìm kiếm nhị phân đã sửa đổi để tìm phần tử thứ k. Cụ thể, hãy xem các phần tử đầu tiên và cuối cùng của TreeSet, sau đó (nếu có thể cho nội dung), hãy chọn một số phần tử nằm giữa hai phần tử và chuyển nó thành đối số tailSet để xem các phần tử của tập sau trung điểm. Sử dụng số lượng các phần tử trong tailSet, sau đó bạn có thể quyết định xem bạn đã tìm thấy phần tử hay không hoặc khám phá nửa trái hoặc phải của cây. Đây là một chút sửa đổi interpolation search trên cây, và có khả năng có thể được nhanh chóng. Tuy nhiên, tôi không biết sự phức tạp bên trong của các phương pháp tailSet, vì vậy điều này có thể thực sự tồi tệ hơn so với cây thống kê thứ tự. Nó cũng có thể thất bại nếu bạn không thể tính toán "điểm giữa" của hai phần tử, ví dụ: nếu bạn đang lưu trữ String s trong số TreeSet của mình.

Hy vọng điều này sẽ hữu ích!

Answer 4

[Dưới đây, tôi viết tắt "hoạt động tìm kiếm yếu tố thứ k nhỏ nhất" là "thứ K op."]

Bạn cần phải cung cấp thêm chi tiết. Cấu trúc dữ liệu của bạn sẽ cung cấp những hoạt động nào? là K trong Hoạt động Kth rất nhỏ so với N hoặc nó có thể là gì không? Bạn sẽ có bao nhiêu lần chèn thêm & xóa so với tra cứu? Bạn sẽ thường xuyên có số lần tìm kiếm phần tử nhỏ nhất là bao nhiêu lần so với số lần tìm kiếm? Bạn đang tìm kiếm một giải pháp nhanh chóng của một vài dòng trong thư viện Java, hay bạn sẵn sàng bỏ ra một số nỗ lực để xây dựng một cấu trúc dữ liệu tùy chỉnh?

Các hoạt động để cung cấp có thể là bất kỳ tập hợp con của:

• Lookup (tìm một phần tử bằng cách chủ chốt; nơi quan trọng là có thể so sánh và có thể là bất cứ điều gì)

• Chèn

• Xóa

• thứ K

Dưới đây là một số khả năng:

• Nếu có sẽ không có/rất ít chèn & xóa, bạn chỉ có thể sắp xếp các yếu tố và sử dụng một mảng, với O (Đăng nhập (N)) tra cứu thời gian và O (1) cho Kth.

• Nếu O (Log (N)) cho Lookup, Chèn, Xóa và O (k) cho thứ K op. là đủ tốt, có lẽ việc thực hiện dễ nhất sẽ là Skip Lists. (Bài viết trên Wikipedia là rất tốt nếu bạn cần biết thêm chi tiết)

• Nếu K đủ nhỏ, hoặc thứ K hoạt động sẽ chỉ đến sau khi "chèn & xóa giai đoạn" bạn có thể giữ nhỏ K yếu tố trong một đống, sắp xếp sau khi chèn thêm & xóa cho O (N + k Log k) thời gian.(Bạn cũng sẽ cần một Hash riêng biệt cho Lookup)

• Nếu K là tùy ý và O (N) là đủ tốt cho thứ K hoạt động, bạn có thể sử dụng một Hash cho O (1) tra cứu thời gian và sử dụng thuật toán "một mặt-QuickSort" cho các hoạt động Kth (ý tưởng cơ bản là sắp xếp nhanh nhưng trên mỗi phân chia nhị phân chỉ chấp nhận ở bên bạn thực sự cần; tổng đơn giản hóa) N (1/2 + 1/4 + 1/8 + ...) = O (N) thời gian dự kiến)

• Bạn có thể xây dựng một "đơn giản" Interval Tree cấu trúc Augmented với mỗi nút giữ số lượng con cái mình vậy mà Lookup, Chèn, Xóa, thứ K tất cả các tính toán trong O (Log N) thời gian miễn là cây được cân bằng nhưng có lẽ nó sẽ không khó thực hiện nếu bạn là người mới.

v.v ... Bộ thay thế là vô hạn khi có thể diễn giải câu hỏi của bạn.

Answer 5

Bạn có thể sử dụng ConcurrentSkipListSet và sử dụng phương thức toArray() không? ConcurrentSkipListSet được sắp xếp theo thứ tự các phần tử tự nhiên. Điều duy nhất tôi không chắc chắn về là nếu toArray() là O (n) hoặc vì nó được hỗ trợ bởi một List (được hỗ trợ bởi một mảng, như ArrayList) đó là O (1).

Nếu toArray() là O (1) bạn sẽ có thể là một skipList.toArray() [k] để lấy phần tử nhỏ nhất thứ k.

Answer 6

Tôi gặp sự cố tương tự. Vì vậy, tôi lấy mã nguồn của java.util.TreeMap và viết IndexedTreeMap. Nó thực hiện của riêng tôi IndexedNavigableMap:

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

Việc thực hiện dựa trên việc cập nhật trọng lượng nút trong cây đỏ-đen khi nó được thay đổi. Trọng lượng là số lượng các nút con bên dưới một nút nhất định, cộng với một - tự. Ví dụ khi một cây có thể xoay sang trái:

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 chỉ đơn giản là cập nhật trọng lượng lên vào thư mục gốc:

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

Và khi chúng ta cần phải tìm ra nguyên tố theo chỉ số ở đây là việc thực hiện rằng sử dụng trọng lượng:

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); 
} 

Cũng có rất tiện dụng tìm kiếm các chỉ số của một phím:

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; 
} 

Bạn có thể tìm thấy kết quả của tác phẩm này tại http://code.google.com/p/indexed-tree-map/. Đã chuyển đến https://github.com/geniot/indexed-tree-map

Answer 7

Tôi biết câu hỏi này khá cũ, nhưng vì TreeSet triển khai NavigableSet, bạn có quyền truy cập vào phương thức nhóm con chạy trong thời gian không đổi.

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

Cuộc gọi đầu tiên() mất thời gian log (n) trong đó n là kích thước của tập gốc. Điều này tạo ra một số đối tượng không cần thiết có thể tránh được với việc triển khai TreeSet mạnh mẽ hơn, nhưng tránh sử dụng thư viện của bên thứ ba.