Có triển khai hàng đợi (PriorityQueue) cũng là một Tập hợp không?

Question

Tôi đang tìm kiếm triển khai PriorityQueue cũng là Set.

Việc triển khai compareTo nếu các thành phần của nó không được yêu cầu phải phù hợp với việc triển khai equals.

Có nơi nào đó triển khai cho java không?

Cập nhật: Tôi đã triển khai ngay bây giờ bằng cách sử dụng SortedSet làm bộ sưu tập nội bộ. Vì vậy, tôi chỉ phải thực hiện các phương thức còn thiếu để thỏa mãn giao diện hàng đợi. Tôi cũng quên đề cập rằng nó cũng phải là một hàng đợi bị chặn, vì vậy nó có khả năng và loại bỏ phần tử cuối cùng của bộ nếu đạt được dung lượng.

Answer 1

Vâng PriorityQueue đang xảy ra với chính nó phụ thuộc vào các Comparitor hoặc trật tự tự nhiên của mặt hàng để phân loại của nó, tương tự như vậy các Set sẽ phụ thuộc vào thứ tự tự nhiên hoặc Comparitor chức năng vì vậy không tôi không nghĩ rằng một tồn tại như một phần của cài đặt Java mặc định ...

Nhưng bạn có thể tạo một cách dễ dàng nếu tốc độ không phải lo lắng bằng cách thực hiện các giao diện bạn muốn, và sử dụng hậu quả tự nhiên của chúng, v.v ... aka

MyQueueSet extends PriorityQueue implements Set { 
    HashSet set; 
    ... 
} 

Thật không may Java java.util . * Các lớp tập dữ liệu không phải lúc nào cũng dễ dàng nhất để mở rộng mà không cần viết lại các đoạn mã của chúng.

Các PriorityQueue ủng hộ là một đống sắp xếp danh sách các yếu tố, do đó chèn một yếu tố mới và sau đó thực hiện một thử nghiệm contains(e) sẽ là O (n) tìm kiếm bởi vì phân loại là dựa trên xếp hàng, không trên giá trị dữ liệu, nếu bạn bao gồm HashSet để hỗ trợ chức năng Set, bạn có thể cải thiện thời gian tra cứu của mình với chi phí duy trì tham chiếu tập dữ liệu hai lần (nhớ rằng Java là giá trị vượt qua và tất cả các đối tượng sống trên heap). Điều này sẽ cải thiện hiệu suất của một bộ lớn.

Answer 2

Nếu đủ để có hàng đợi có hành vi 'Giống như', thì bạn không muốn chấp nhận mục trùng lặp, thì tôi nghĩ, một giải pháp dễ dàng có thể là phân lớp PriorityQueue và ghi đè add(), addAll() và offer() phương pháp như:

@Override 
public boolean offer(E e) { 
    if (contains(e)) { 
    return false; 
    } else { 
    return super.offer(e); 
    } 
} 

BTW - add() cuộc gọi offer() nội bộ, như vậy có lẽ nó thậm chí còn đủ để chỉ ghi đè lên các phương pháp offer() và làm việc kiểm tra đó.

Answer 3

Ưu tiênQueue là một AbstractCollection - điều này có giao diện gần như giống hệt với Tập hợp. Tôi chắc chắn nó sẽ dễ dàng để làm cho một wrapper chuyển đổi một PriorityQueue thành một Set. Bạn có thể giữ một bảng băm bên của các phần tử được chèn để tránh trùng lặp, nếu bạn thực sự cần thực thi điều đó.

Tôi không nghĩ PriorityQueue yêu cầu compareTo phải nhất quán với bằng. PriorityQueue không sử dụng bằng tất cả (ngoại trừ các hoạt động AbstractCollection được thừa hưởng của nó?).

Answer 4

TreeSet là một bộ cung cấp trình vòng lặp có thứ tự.Nó thực hiện giao diện SortedSet, đảm bảo rằng trình lặp được trả về theo phương thức iterator sẽ trả về các phần tử của bộ theo thứ tự tăng dần được xác định theo thứ tự tự nhiên của chúng (thông qua Comparable), hoặc được xác định bởi một bộ so sánh được đặt cho nó.