Khôi phục lại java.util.PriorityQueue sau khi cập nhật các thành phần

Question

Tôi có một tham chiếu PriorityQueue chứa một số đối tượng. Khi tôi chèn các phần tử vào hàng đợi ưu tiên, thứ tự được duy trì bởi cấu trúc dữ liệu. Bây giờ sau khi một hoạt động loại bỏ tôi cập nhật một số tài liệu tham khảo đang được tổ chức bởi hàng đợi ưu tiên. Lý tưởng nhất điều này đòi hỏi một hoạt động reheapify trên hàng đợi ưu tiên nhưng như là rõ ràng kể từ khi tôi sửa đổi tài liệu tham khảo được lựa chọn bên ngoài một reheapify không thể được kích hoạt. Vì vậy, cách tốt nhất để đảm bảo rằng tôi có thể có được những lợi thế của một đống như nhanh chóng trích xuất tối đa trong sự hiện diện của sửa đổi các yếu tố tùy ý bên trong hàng đợi là gì? Tôi thấy tôi cần cấu trúc dữ liệu tốt hơn?

Để cụ thể hơn, tôi cần thực hiện một thứ gì đó giống như một đống Fibonacci trong Java. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Tính năng này có sẵn không?

Answer 1

Bạn có thể sử dụng cây của riêng mình cho phép các thành phần trùng lặp thay vì đống. Dễ dàng hơn, bạn có thể sử dụng TreeMap<PriorityKey, LinkedHashSet<Value>>. Tất cả các hoạt động này là O (log priorityType):

• thêm là get(priority).add(value), nếu nhận được trả về null, put(priority, new LinkedHashSet())
• loại bỏ một yếu tố độc đoán là tương tự, ngoại trừ nhu cầu để loại bỏ các ưu tiên ra khỏi bản đồ nếu Set là trống.
• cuộc thăm dò() là

-

Entry<PriorityKey, LinkedHashSet<Value>> e = map.firstEntry(); 
if (e==null) return null; 
Iterator<Value> i = e.getValue().iterator(); 
Value v = i.next(); //must always have at least one element. 
i.remove(); 
if (!i.hasNext()) map.remove(e.getKey()); 
return v; 

Tuy nhiên nếu bạn cần thay đổi các ưu tiên bạn phải gỡ bỏ và thêm phần tử.

Answer 2

Có thể một NavigableMap phù hợp với nhu cầu của bạn: dễ dàng nhận dạng phần tử "cao nhất" hoặc "thấp nhất", chèn nhanh và thời gian truy cập và bạn có thể cập nhật giá trị dễ dàng.

http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html

TreeMap thực hiện NavigableMap, và do đó cung cấp các firstEntry/lastEntry phương pháp, và nhiều hơn nữa.