如何在python中實現一個自定義類的優先級隊列？

我從Java的背景，我需要這樣的如何在python中實現一個自定義類的優先級隊列？

public class Item implements Comparable<Item> { 

    int score; 
    ArrayList<Integer> arr; 

    @Override 
    public int compareTo(Item o2) { 
     return score != o2.score ? score - o2.score : arr.size() - o2.arr.size(); 
    } 


    public static void main(String[] args) { 
     PriorityQueue<Item> p = new PriorityQueue<Item>(); 

    } 
}

所以我有兩個變量，評分和列表的一類。對於自然排序也有計算。

請問有人請告訴我如何做到這一點蟒蛇？ heapq不適用於我，因爲我的分數函數根據兩個變量而不是一個來檢查分數。

來源

2015-09-09 Dude

你很幸運，因爲實施already exists。

請確保遵循常規條目結構並使用(priorities_tuple, entry)形式的元組將優先級附加到插入到隊列中的所有條目。

一個例子：

import Queue 
import random 
pq = Queue.PriorityQueue() 
todos = ["eat", "sleep", "python"] 
# obvously replace random with your 
todos_with_priorities = [((random.random(),), e) for e in todos] 
for e in todos: 
    pq.put(e)

消耗隊列像這樣：

priorities, item = pq.get()

爲了形成越來越複雜的優先級添加更多的成員元組結構。在你的情況下，元組應該是這樣的：((e.score, len(e.arr)), e)。

來源

2015-09-09 23:02:27

但是，如果我的數據是在元組的形式，我不能處理與comareTo上面不同的tite break？ – Dude

@Dude看看編輯。告訴我你是否錯過了一些東西。 –

'Queue'中的'PriorityQueue'附帶額外的行李（它是線程安全的）。如果性能是一個問題，那麼我建議爲['heapq']（https://docs.python.org/3/library/heapq.html）模塊創建一個類封裝器。 – Dunes

如何在python中實現一個自定義類的優先級隊列？

回答

相關問題