使Java PriorityQueue進入一個穩定的優先級隊列

我試圖在Java中實現一個穩定的（先入先出）優先級隊列。假設，關鍵是出了名，值是一個年齡，我知道我可以做這樣一個不穩定的優先級隊列：使Java PriorityQueue進入一個穩定的優先級隊列

Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(100, ageComparator);

這確實非常的一切，我需要它，但它不在我插入（或刪除它們）時維護鍵值對的順序。

我發現一個「解決方法」是通過創建一個LinkedList，它提供了基本上所有相同的功能，除了它不包含帶有比較器選項的構造函數，我覺得它必須更慢我通過在每個隊列操作後調用Collections.sort()來維護價值排序。

所以我想這實際上有兩個我感興趣的選項。首先，我如何編輯上面的PriorityQueue以保持插入和移除順序？或者第二，如何強制我的LinkedList選項立即使用比較器，而不必在每個操作上調用排序？謝謝！

編輯：

感謝您發佈第一條評論中的好問題。通過FIFO，我的意思是對於具有相同值的鍵值對，首先應該先提取先置入的那一對。

來源

2014-02-07 Free

你究竟調用的是FIFO優先級隊列？你是否認爲它是同等重要項目的FIFO？ –

@JimGarrison - 好問題;是的，這就是我的意思。所以，如果我插入（「愛麗絲」，30），然後（「鮑勃」，30），然後提取應該給我愛麗絲，然後鮑勃。 – Free

你需要的東西是這樣的：

import java.util.AbstractMap; 
import java.util.Comparator; 
import java.util.PriorityQueue; 
import java.util.concurrent.atomic.AtomicInteger; 

public class PriorityTest { 
    @SuppressWarnings("serial") 
    private static class Entry extends AbstractMap.SimpleEntry<String, Integer> { 
    private final static AtomicInteger seq = new AtomicInteger(0); 
    final int order; 
    public Entry(final String _key, final Integer _value) { 
     super(_key, _value); 
     order = seq.incrementAndGet(); 
    } 
    } 

    private static class OrderedComparator implements Comparator<Entry> { 
    @Override 
    public int compare(final Entry _e1, final Entry _e2) { 
     int r = _e1.getValue().compareTo(_e2.getValue()); 
     if (r == 0) 
     return Integer.compare(_e1.order, _e2.order); 
     return r; 
    } 
    } 

    public static void main(String[] args) { 
    final PriorityQueue<Entry> pq = new PriorityQueue<Entry>(10, new OrderedComparator()); 
    pq.add(new Entry("Jane", 22)); 
    pq.add(new Entry("John", 15)); 
    pq.add(new Entry("Bill", 45)); 
    pq.add(new Entry("Bob", 22)); 
    while(!pq.isEmpty()) { 
     System.out.println(pq.remove()); 
    } 
    } 
}

來源

2014-03-29 10:26:00 user3159253

Keap-based PriorityQueue自然是穩定的。它是用Kotlin編寫的，因此它可以用Java代碼代替java.util.PriorityQueue。

來源

2016-12-04 11:09:53

使Java PriorityQueue進入一個穩定的優先級隊列

回答

相關問題