CODEWITHSUNDEEP
python
Sahil
Sahil

Reputation: 9496

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

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.

Upvotes: 3

Views: 3017

Answers (1)

Reut Sharabani
Reut Sharabani

Reputation: 31349

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).

Upvotes: 5

Related Questions