# Heapq module of Python module

2022-01-29 21:29:13

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