amirhossein
amirhossein

Reputation: 39

priority queue in Python using comparator

Is there any way exists that can do the java queue priority comparator.comparingInt method in Python?

I want the node which has a higher priority come to the front of the queue.

edited: for example:

class node:
  def __init__(self, label, priority):
      self.label = label
      self.priority = priority
  




node1 = node('a', 3)
node2 = node('b',2)
node3 = node('c', 1)
 
nodes in queue comes like this==> (node1,node2,node3)

Upvotes: 1

Views: 1301

Answers (2)

BrokenBenchmark
BrokenBenchmark

Reputation: 19262

As Albin states, you'll need to use the heapq module (unless you want to write your own heap implementation from scratch). One very important thing to note is that this library gives only an implementation of a min-heap, rather than a max-heap.

To write a comparator for a custom object, you'll need to override the __lt__ function (the function that's called when the < operator is used). So your node class would look like this:

class node:
  nodes = dict()

  def __init__(self, label, priority):
      self.label = label
      self.priority = priority
  
  def __lt__(self, other):
      # Note that we've reversed the operands here, since we want a max-heap.
      return other.priority < self.priority

Then, we can make a heap as follows:

import heapq

heap = []

node1 = node('a', 3)
node2 = node('b', 2)
node3 = node('c', 1)

heapq.heappush(heap, node1)
heapq.heappush(heap, node2)
heapq.heappush(heap, node3)

# Should print 'a', 'b', 'c' in that order.
for i in range(3):
    print(heapq.heappop(heap).label)

Upvotes: 2

Albin Sid&#229;s
Albin Sid&#229;s

Reputation: 365

You should look closer on this documentation regarding priority queues (heapq for python3): https://docs.python.org/3/library/heapq.html#heapq.heapify

It refers to the priority queue and also have basic examples of sorting based on a value inside a tuple.

Upvotes: 0

Related Questions