Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

1. Heqpq is introduced

A heap is a nonlinear tree data structure with two types of heap, maximum heap and minimum heap. Python’s HEAPq module defaults to the minimum heap. The most important feature of heap data structures is that heap[0] is always the smallest element.

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

Minimum heap: A tree in which the value of the parent node is always greater than or equal to any child node

We generally use binary heap to implement priority queue, whose internal adjustment algorithm complexity is logN

2. Method introduction

2.1 heappush method

Heappush (heap, item) : Pushes an item into the heQP.

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

result:

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

2.2 heappop method

Heappop (heap) : Pops the minimum value from the heap item.

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

result:

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

print(heapq1)
Copy the code

result:

1
Copy the code

Note: If you append a value by heAPq instead of pressing it into the heap, the heap function cannot manipulate the element, or the element is not aware of the heap. Here’s a concrete example:

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

result:

1
Copy the code

A before and after comparison shows that -1 is not sensed by the heap, otherwise the smallest element that pops up would be -1 instead of 1

2.3 heapify method

Heapq.heapify (list): The argument must be list, and this function must turn the list into a heap, operating in real time.

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

result:

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

After processing, list1 has become the heap (smallest element 1 is first)

2.4 heappushpop method

Heappushpop (Heap, item) : heapPush (heap, item) and HeapPOP (heap)

2.4.1 Effect of HEAPPush + HeAPPOP

Heappush first

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

result:

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

Heappop again

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

result:

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

2.4.2 Effect of HeapPushPop

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

result:

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

2.5 heapreplace method

Heapreplace (Heap, item) : a combination of heapPOP and Heappush, heapPOP (heap) and heappush(Heap, item)

Note the difference between this method and the HeappushPOP method

2.5.1 Effect of HEAPPOP + HeapPush

First heappop

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

result:

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

Heappush again

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

result:

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

2.5.2 Effect of Heapreplace

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

result:

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

2.6 the merge method

Merge (*iterables): Merges multiple heaps

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

result:

<generator object merge at 0x0000024280537748>
Copy the code

As you can see, this method returns a generator whose contents can be retrieved using either the iteration or list() method

print(list(new_heapq))
Copy the code

result:

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

2.7 nlargest method

Heapq. nlargest(n, iterable): Obtain the largest n values in iterable

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

result:

[8, 7)Copy the code

Here we get the largest two numbers in list1

2.8 nsmallestmethods

Heapq. nsmallest(n, iterable): Retrieves the largest n values of the iterable

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

result:

[1, 2]
Copy the code

The nlargest() and nsmallest() functions are suitable for the nlargest and nsmallest() methods when the number of elements to find is relatively small. If you only want to find the unique smallest or largest (N=1) element, it is faster to use the min() and Max () functions. Similarly, if N is close to the set size, it is usually faster to sort the set first and then slice it (sorted(items)[:N] or sorted(items)[-n :]). The nlargest() and nsmallest() functions need to be used in the right context to take advantage of them (sorting is better if N is approaching the set size).