# Some applications of heapq module of Python module

2022-01-30 00:32:18

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