python tutorial - Python - data structure priority queue and heapq - learn python - python programming




Priority Queue

  • A priority queue is an abstract data type (ADT) which is like a regular queue or stack data structure, but where additionally each element has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
  • While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like a list or a map; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

Sample A - simplest

  • The following code the most simplest usage of the priority queue.
try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

q = Q.PriorityQueue()
q.put(10)
q.put(1)
q.put(5)
while not q.empty():
	print q.get(),
click below button to copy the code. By Python tutorial team

Output:

1 5 10 
  • As we can see from the output, the queue stores the elements by priority not by the order of element creation. Note that depending on the Python versions, the name of the priority queue is different. So, we used try and except pair so that we can adjust our container to the version.
  • The priority queue not only stores the built-in primitives but also any objects as shown in next section.

Sample B - tuple

  • The priority queue can store objects such as tuples:
try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

q = Q.PriorityQueue()
q.put((10,'ten'))
q.put((1,'one'))
q.put((5,'five'))
while not q.empty():
    print q.get(),
click below button to copy the code. By Python tutorial team

Output:

(1, 'one') (5, 'five') (10, 'ten')

Sample C - class objects using __cmp__()

  • Python isn't strongly typed, so we can save anything we like: just as we stored a tuple of (priority,thing) in previous section. We can also store class objects if we override __cmp__() method:
try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

class Skill(object):
    def __init__(self, priority, description):
        self.priority = priority
        self.description = description
        print 'New Level:', description
        return
    def __cmp__(self, other):
        return cmp(self.priority, other.priority)

q = Q.PriorityQueue()

q.put(Skill(5, 'Proficient'))
q.put(Skill(10, 'Expert'))
q.put(Skill(1, 'Novice'))

while not q.empty():
    next_level = q.get()
    print 'Processing level:', next_level.description
click below button to copy the code. By Python tutorial team

Output:

New Level: Proficient
New Level: Expert
New Level: Novice
Processing level: Novice
Processing level: Proficient
Processing level: Expert

heapq - Heap queue

  • The heapq implements a min-heap sort algorithm suitable for use with Python's lists.
import heapq

heap = []
heapq.heappush(heap, (1, 'one'))
heapq.heappush(heap, (10, 'ten'))
heapq.heappush(heap, (5,'five'))

for x in heap:
	print x,
print

heapq.heappop(heap)

for x in heap:
	print x,
print 

# the smallest
print heap[0]
click below button to copy the code. By Python tutorial team

Output

(1, 'one') (10, 'ten') (5, 'five')
(5, 'five') (10, 'ten')
(5, 'five')

heapq - heapify

  • We can Transform list $x$ into a heap, in-place, in linear time:

Sample Code

heapq.heapify(x)
click below button to copy the code. By Python tutorial team

Example

import heapq

heap = [(1, 'one'), (10, 'ten'), (5,'five')]
heapq.heapify(heap)
for x in heap:
	print x,
print

heap[1] = (9, 'nine')
for x in heap:
	print x,
click below button to copy the code. By Python tutorial team

Output:

(1, 'one') (10, 'ten') (5, 'five')
(1, 'one') (9, 'nine') (5, 'five')

Note that we replaced (10, 'ten') with (9, 'nine').


Related Searches to Python - data structure priority queue and heapq