current position:Home>Some applications of heapq module of Python module

Some applications of heapq module of Python module

2022-01-30 00:32:18 Never forget without thinking

Little knowledge , Great challenge ! This article is participating in “ A programmer must have a little knowledge ” Creative activities .

This article has participated in 「 Digging force Star Program 」, Win a creative gift bag , Challenge creation incentive fund .

Heap is a nonlinear tree data structure , Yes 2 Seed pile , Maximum heap and minimum heap .python Of heapq The module defaults to the minimum heap . The most important feature of heap data structure is heap[0] Always the smallest element .

The biggest pile : The value of the parent node in the tree is always greater than or equal to the value of any child node

The smallest pile : The value of the parent node in the tree is always greater than or equal to the value of any child node

We usually use binary heap to implement priority queue , Its internal adjustment algorithm complexity is logN

1. Heap sort problem

1.1 utilize heappush+heappop

import heapq
​
​
def sorted_func(iterable):
    new_list = []
    for element in iterable:
        heapq.heappush(new_list, element)
    return [heapq.heappop(new_list) for _ in range(len(new_list))]
​
​
if __name__ == '__main__':
    list1 = [5, 8, 3, 9, 0, -3, 12, 4, 8]
    print(sorted_func(list1))
 Copy code 

result:

[-3, 0, 3, 4, 5, 8, 8, 9, 12]
 Copy code 

1.2 utilize nlargest or nsmallest

import heapq
​
list1 = [5, 8, 3, 9, 0, -3, 12, 4, 8]
print(heapq.nsmallest(len(list1), list1))
 Copy code 

result:

[-3, 0, 3, 4, 5, 8, 8, 9, 12]
 Copy code 

Use nlargest It's equivalent to sorting from large to small , and nlargest Use consistent , No more details here

1.3 utilize heapify

import heapq
​
list1 = [5, 8, 3, 9, 0, -3, 12, 4, 8]
heapq.heapify(list1)
print(list1)
 Copy code 

result:

[-3, 0, 3, 4, 8, 5, 12, 9, 8]
 Copy code 

2. Priority queue problem

import heapq
​
​
class PriorityQueue(object):
​
    def __init__(self):
        self._queue = []
        self.index = 0
​
    def push(self, priority, item):
        heapq.heappush(self._queue, (-priority, self.index, item))
        self.index += 1
​
    def pop(self):
        return heapq.heappop(self._queue)[-1]
​
​
if __name__ == '__main__':
    q = PriorityQueue()
    q.push(2, 'two')
    q.push(1, 'one')
    q.push(-2, 'fei')
    q.push(12, '123')
    print(q.pop())
    print(q.pop())
 Copy code 

result:

123
two
 Copy code 

In the above code , The queue contains (-priority, index, item) tuples . Negative priority numbers are used to sort from high to low . Set up index Variables are used to ensure the correct ordering of elements with the same priority , Here, the same priority will be sorted according to the insertion order ( Of course , You can also arrange them in reverse order of insertion , as long as -index Can . Or you can customize the sorting method to replace index). and ,index Variables are the same Priority elements play an important role in comparison .

2.2 Explanation

To illustrate this , So let's do an example , hypothesis item Sort is not supported .

class Item:
    def __init__(self, name):
        self.name = name
    def __repr__(self):
        return 'Item({!r})'.format(self.name)
 Copy code 
a = Item('a')
b = Item('b')
print(a < b)
 Copy code 

result:

Traceback (most recent call last):
  File "D:/interview/interview/22.py", line 11, in <module>
    print(a < b)
TypeError: '<' not supported between instances of 'Item' and 'Item'
 Copy code 

2.2.1 (priority, item) The case of binary tuples

If you use tuples (priority, item) , As long as the priorities of the two elements are different, we can compare . But if two elements have the same priority , Then the comparison operation will make the same error as before

a = (1, Item('a'))
b = (2, Item('b'))
print(a < b)
 Copy code 

result:

True
 Copy code 
c = (1, Item('first'))
print(a < c)
 Copy code 

result:

Traceback (most recent call last):
  File "D:/interview/interview/22.py", line 13, in <module>
    print(a < c)
TypeError: '<' not supported between instances of 'Item' and 'Item'
 Copy code 

2.2.2 (priority, index, item) The case of ternary tuples By introducing another index Variables form triples (priority, index, item) , Can well avoid the above mistakes , Because it's impossible for two elements to have the same index value .Python When doing tuple comparison , If the previous comparison can confirm the result , The following comparison operation will not happen .

a = (1, 0, Item('a'))
b = (2, 1, Item('b'))
print(a < b)
 Copy code 

result:

True
 Copy code 
c = (1, 2, Item('first'))
print(a < c)
 Copy code 

result:

True
 Copy code 

in addition , If you want to use the same queue in multiple threads , Then you need to add appropriate locking and semaphore mechanisms .

copyright notice
author[Never forget without thinking],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201300032169411.html

Random recommended