2015-09-09 40 views
0

我從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不適用於我,因爲我的分數函數根據兩個變量而不是一個來檢查分數。

回答

3

你很幸運,因爲實施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)

+0

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

+0

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

+0

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