如何在Python中使用自定义类实现优先队列？

Question

我来自Java背景，我需要做类似于这样的事情

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>();

    }
}

我有一个类，其中有两个变量：分数和列表。还有一个自然排序的计算。

请问有人能告诉我如何在Python中实现它？heapq对我无效，因为我的得分函数基于两个变量而不是一个。

- Max

Answer 1

因为已经有一个实现存在，所以你很幸运。

确保遵循条目的常规结构，并使用形如(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)。

- Reut Sharabani

---

但是如果我的数据是以元组的形式存在，我就无法像上面的comareTo一样处理标题中断了？ - Max

@兄弟，看一下修改。告诉我是否有遗漏的内容。 - Reut Sharabani

Queue 中的 PriorityQueue 带有额外的负担（它是线程安全的）。如果性能是一个问题，那么我建议为 heapq 模块创建一个类包装器。 - Dunes