Làm thế nào để lặp qua một PriorityQueue?

Question

for (Event e : pq) 

không lặp lại theo thứ tự ưu tiên.

while(!pq.isEmpty()){ 
    Event e = pq.poll(); 
} 

Thao tác này nhưng làm trống hàng đợi.

Answer 1

Từ Javadocs:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()) .

Có lẽ cơ chế tương đương khác.

Answer 2

Phương thức peek() không xóa bất kỳ thứ gì khỏi hàng đợi, nhưng vì lý do này, nó sẽ liên tục nhận được giá trị cao nhất cho đến khi nó trống. Tôi đoán bạn đã kiểm tra xem nó có trống không sau vòng lặp while, điều này sẽ cho bạn kết luận này.

Cách duy nhất để làm điều này là tự mình sắp xếp. Bạn có thể lấy so sánh ban đầu cho nó như thế này:

Event[] events = Arrays.sort(pq.toArray(), pq.comparator()); 
for (Event e : events) { 
    // do stuff 
} 

Answer 3

Hàng đợi ưu tiên dựa trên heap chỉ đảm bảo rằng phần tử đầu tiên là phần tử cao nhất/thấp nhất. Không có giá rẻ (tức là O (n)) cách để có được các yếu tố trong hình thức được sắp xếp.

Nếu bạn cần thực hiện việc này thường xuyên, hãy xem xét sử dụng cấu trúc duy trì các yếu tố trong biểu mẫu được sắp xếp. Ví dụ, sử dụng java.util.TreeSet, và sử dụng một trong hai pollFirst() hoặc pollLast() ở vị trí của peek()/poll()

Answer 4

Bạn không thể đi theo một hàng đợi ưu tiên theo thứ tự mà vì tình hình thực hiện cơ bản (Tôi nghĩ đó là min-heap trong Java). Nó không phải là một mảng được sắp xếp để bạn chỉ có thể đi từ một phần tử đến một phần tử có mức độ ưu tiên thấp hơn. Nhìn trộm là thời gian không đổi vì nó nhìn vào phần tử nhỏ nhất. Để có được cái tiếp theo (trong thời gian O (log n)), bạn phải dequeue yếu tố nhỏ nhất, đó là cách nó hoạt động. Dequeing không chỉ là vấn đề lấy yếu tố đó ra ngoài, cấu trúc bên dưới sắp xếp lại chính nó để mang lại yếu tố có ưu tiên thấp nhất trước tiên.

Ngoài ra, để đi qua toàn bộ hàng đợi ưu tiên là hoạt động O (n log (n)). Vì vậy, bạn cũng có thể chỉ cần lấy tất cả các yếu tố trong hàng đợi và sắp xếp chúng (cũng O (n log (n))) và sau đó bạn có thể đi qua chúng như bạn muốn. Nhược điểm duy nhất là bạn đang nắm giữ một bản sao của hàng đợi.

Tuy nhiên, nếu bạn cần truyền dữ liệu theo cách này, hàng đợi ưu tiên có thể không phải là cấu trúc dữ liệu phù hợp với nhu cầu của bạn.

Answer 5

Gần đây, tôi có cùng một vấn đề. Tôi muốn sử dụng một số đối tượng cụ thể từ hàng đợi ưu tiên và sau đó giữ nguyên các phần tử còn lại.

1) Tôi đã tạo mớiPriorityQueue. 2) Iterator được sử dụng để phân tích mọi phần tử trong oldQueue 3) sử dụng phương thức oldQueue.poll() để truy xuất phần tử 4) chèn phần tử 3) vào newPriorityQueue nếu không được sử dụng.

Queue<String> newQueue = new PriorityQueue<String>(); 
    // Assuming that oldQueue have some data in it. 

    Iterator<String> itr = oldQueue.iterator(); 
    while(itr.hasNext()){ 
     String str = oldQueue.poll(); 
     // do some processing with str 
     if(strNotUsed){ 
      newQueue.offer(str); 
     } 
    } 

Cuối cùng, oldQueue sẽ trống. @ Khác: - hãy đề xuất một cách tốt hơn nếu tôi có thể làm điều tương tự. Tôi không thể sử dụng iterator vì nó không trả về các phần tử theo đúng thứ tự.

Answer 6

Bạn có thể tạo một bản sao của hàng đợi và thăm dò trong vòng một, trong ví dụ pq này là hàng đợi ưu tiên ban đầu:

PriorityQueue<Your_class> pqCopy = new PriorityQueue<Your_class>(pq); 
while(!pqCopy.isEmpty()){ 
    Your_Class obj = pqCopy.poll(); 
    // obj is the next ordered item in the queue 
    ..... 
} 

Answer 7

for (Event event: pq.toArray(new Event[pq.size()])) { 
    event.toString(); 
} 

Answer 8

Vì vậy, lấy priorityQueue trong một danh sách và sau đó sắp xếp nó là một lựa chọn tốt như đã đề cập ở trên. Dưới đây là một số chi tiết lý do tại sao trình vòng lặp cho kết quả không mong muốn:

Trình lặp không trả về các phần tử theo thứ tự đúng vì nó in từ cấu trúc dữ liệu cơ bản (tương tự như ArrayList). ArrayList có dữ liệu được lưu trữ trong nó giống như cách dữ liệu được lưu trữ trong một thực hiện Mảng BinaryHeap. Ví dụ:

PriorityQueue<Integer> pq = new PriorityQueue<>(); 
ArrayList<Integer> test = new ArrayList(Arrays.asList(6,12,7,9,2)); 
test.forEach(x -> pq.add(x)); 
System.out.println("Priority Queue:- "+pq); [2, 6, 7, 12, 9] 

nơi childOf (i) là 2 * i + 1 và 2 * i + 2 và parentOf (i) là (i-1)/2