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 .

1.heqpq Introduce

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

2. Methods to introduce

2.1 heappush Method

heappush(heap, item)： take item Push into the reactor heqp in .

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq.heappush(list1, 12)
print(list1)
 Copy code 

result:

[1, 3, 5, 2, 6, 8, 9, 3, 12]
 Copy code 

2.2 heappop Method

heappop(heap)： From the heap item Pop up minimum .

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq1 = heapq.heappop(list1)
print(list1)
 Copy code 

result:

[3, 2, 5, 3, 6, 8, 9]
 Copy code 

print(heapq1)
 Copy code 

result:

1
 Copy code 

notes ： If it wasn't pressed into the pile , But through heapq Append a value , Heap functions cannot operate on this element , Or the element is imperceptible to the heap . Let's take a specific example ：

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
list1.append(-1)
heapq2 = heapq.heappop(list1)
print(heapq2)
 Copy code 

result:

1
 Copy code 

Before and after comparison, we can find ,-1 Not perceived by the heap , Otherwise, the smallest element to pop up should be -1 instead of 1

2.3 heapify Method

heapq.heapify(list): Parameter must be list, This function must set list It's a pile , Real time operation .

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq1 = heapq.heapify(list1)
print(list1)
 Copy code 

result:

[1, 2, 5, 3, 6, 8, 9, 3]
 Copy code 

After processing list1 Has become a heap ( The smallest element 1 Come first )

2.4 heappushpop Method

heappushpop(heap, item)： heappush Methods and heappop Combination of methods , First heappush(heap, item), Again heappop(heap)

2.4.1 heappush+ heappop The effect of

First heappush

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq.heappush(list1, 12)
print(list1)
 Copy code 

result:

[1, 3, 5, 2, 6, 8, 9, 3, 12]
 Copy code 

Again heappop

heapq1 = heapq.heappop(list1)
print(list1)
 Copy code 

result:

[3, 2, 5, 3, 6, 8, 9, 12]
 Copy code 

2.4.2 heappushpop The effect of

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq.heappushpop(list1, 12)
print(list1)
 Copy code 

result:

[3, 2, 5, 3, 6, 8, 9, 12]
 Copy code 

2.5 heapreplace Method

heapreplace(heap, item)： heappop Methods and heappush Combination of methods , First heappop(heap), Again heappush(heap, item)

Note that this method is similar to heappushpop The difference in method

2.5.1 heappop+ heappush The effect of

First heappop

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq1 = heapq.heappop(list1)
print(list1)
 Copy code 

result:

[3, 2, 5, 3, 6, 8, 9]
 Copy code 

Again heappush

heapq.heappush(list1, 12)
print(list1)
 Copy code 

result:

[3, 2, 5, 3, 6, 8, 9, 12]
 Copy code 

2.5.2 heapreplace The effect of

import heapq
​
list1 = [1, 3, 5, 2, 6, 8, 9, 3]
heapq.heapreplace(list1, 12)
print(list1)
 Copy code 

result:

[3, 2, 5, 3, 6, 8, 9, 12]
 Copy code 

2.6 merge Method

merge(*iterables): Merge multiple heaps

import heapq
​
list1 = [1, 3, 5, 7]
list2 = [2, 4, 6, 8]
new_heapq = heapq.merge(list1, list2)
print(new_heapq)
 Copy code 

result:

<generator object merge at 0x0000024280537748>
 Copy code 

It can be seen that , This method will return a generator , You can use iterations or list() Method to get its content

print(list(new_heapq))
 Copy code 

result:

[1, 2, 3, 4, 5, 6, 7, 8]
 Copy code 

2.7 nlargest Method

heapq.nlargest(n, iterable): obtain iterable The largest of n It's worth

import heapq
​
list1 = [1, 3, 5, 7, 2, 4, 6, 8]
print(heapq.nlargest(2, list1))
 Copy code 

result:

[8, 7]
 Copy code 

Here's the acquisition of list1 The largest of 2 Number

2.8 nsmallest Method

heapq.nsmallest(n, iterable): obtain iterable The largest of n It's worth

import heapq
​
list1 = [1, 3, 5, 7, 2, 4, 6, 8]
print(heapq.nsmallest(2, list1))
 Copy code 

result:

[1, 2]
 Copy code 

Here's the acquisition of list1 The smallest of all 2 Number about nlargest Methods and nsmallest Method , When the number of elements to be searched is relatively small , function nlargest() and nsmallest() It's very suitable . If you just want to find the only minimum or maximum （N=1） The elements of the words , So use min() and max() The function will be faster . Allied , If N When the size of is close to the size of the collection , It is usually faster to sort the collection first and then use the slicing operation （sorted(items)[:N] Or is it sorted(items)[-N:]）. You need to use functions in the right place nlargest() and nsmallest() To give full play to their advantages （ If N It's approaching the size of the collection , Then it would be better to use sorting operations ）.