如何在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中实现一个自定义类的优先级队列？

回答

相关问题