How to implement priority queue with a custom class in python?

Question

I am from java background, I need to something like this

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

    }
}

So I have a class which has two variable, score and list. There is a calculation for natural ordering for also too.

Could somebody please tell me how to do it python? heapq does not work for me, because my score function checks score on the basis of two variables not one.

Reut Sharabani · Accepted Answer · 2015-09-09 23:09:06Z

5

You're in luck because an implementation already exists.

Make sure to follow the regular structuring of entries and attach the priority to all entries inserted into the queue using a tuple of the form (priorities_tuple, entry).

An example:

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)

Consume the queue like so:

priorities, item = pq.get()

To form more and more complex priorities add more members to the tuple structure. In your case the tuple should be something like: ((e.score, len(e.arr)), e).

edited Sep 9, 2015 at 23:09

answered Sep 9, 2015 at 23:02

Reut Sharabani

31.5k7 gold badges76 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Sahil Over a year ago

But if my data is in the form of tuple, I can't handle the tite breaking unlike comareTo above?

Reut Sharabani Over a year ago

@Dude look at the edit. Tell me if you're missing something.

Dunes Over a year ago

The PriorityQueue in Queue comes with extra baggage (it's thread safe). If performance is an issue then I'd recommend creating a class wrapper for the heapq module.

Collectives™ on Stack Overflow

How to implement priority queue with a custom class in python?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related