current position:Home>Heapq module of Python module
Heapq module of Python module
2022-01-29 21:29:13 【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 .
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 ).
copyright notice
author[Never forget without thinking],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201292129108061.html
The sidebar is recommended
- Compile D + +, and use d to call C from python
- Install tensorflow and python 3.6 in Windows 7
- Python collects and monitors system data -- psutil
- Python collects and monitors system data -- psutil
- Finally, this Python import guide has been sorted out. Look!
- Quickly build Django blog based on function calculation
- Getting started with Python - object oriented - special methods
- Teach you how to use Python to transform an alien invasion game
- You can easily get started with Excel. Python data analysis package pandas (VI): sorting
- Implementation of top-level design pattern in Python
guess what you like
-
Using linear systems in python with scipy.linalg
-
Python tiktok 5000+ V, and found that everyone love this video.
-
Using linear systems in python with scipy.linalg
-
How to get started quickly? How to learn Python
-
Modifying Python environment with Mac OS security
-
You can easily get started with Excel. Python data analysis package pandas (XI): segment matching
-
Advanced practical case: Javascript confusion of Python anti crawling
-
Better use atom to support jupyter based Python development
-
Better use atom to support jupyter based Python development
-
Fast power modulus Python implementation of large numbers
Random recommended
- Python architects recommend the book "Python programmer's Guide" which must be read by self-study Python architects. You are welcome to take it away
- Decoding the verification code of Taobao slider with Python + selenium, the road of information security
- Python game development, pyGame module, python implementation of skiing games
- This paper clarifies the chaotic switching operation and elegant derivation of Python
- You can easily get started with Excel. Python data analysis package pandas (3): making score bar
- Test Development: self study Dubbo + Python experience summary and sharing
- Python + selenium automated test: page object mode
- You can easily get started with Excel. Python data analysis package pandas (IV): any grouping score bar
- Opencv skills | saving pictures in common formats as transparent background pictures (with Python source code) - teach you to easily make logo
- You can easily get started with Excel. Python data analysis package pandas (V): duplicate value processing
- Python ThreadPoolExecutor restrictions_ work_ Queue size
- Python generates and deploys verification codes with one click (Django)
- With "Python" advanced, you can catch all the advanced syntax! Advanced function + file operation, do not look at regret Series ~
- At the beginning of "Python", you must see the series. 10000 words are only for you. It is recommended to like the collection ~
- [Python kaggle] pandas basic exercises in machine learning series (6)
- Using linear systems in python with scipy.linalg
- The founder of pandas teaches you how to use Python for data analysis (mind mapping)
- Using Python to realize national second-hand housing data capture + map display
- Python image processing, automatic generation of GIF dynamic pictures
- Pandas advanced tutorial: time processing
- How to make Python run faster? Six tips!
- Django: use of elastic search search system
- Fundamentals of Python I
- Python code reading (chapter 35): fully (deeply) expand nested lists
- Python 3.10 official release
- Solution of no Python 3.9 installation was detected when uninstalling Python
- This pandas exercise must be successfully won
- [Python homework] coupling network information dissemination
- Python application software development tool - tkinterdesigner v1.0 5.1 release!
- [Python development tool Tkinter designer]: Lecture 2: introduction to Tkinter designer's example project
- [algorithm learning] sword finger offer 64 Find 1 + 2 +... + n (Java / C / C + + / Python / go / trust)
- leetcode 58. Length of Last Word(python)
- Problems encountered in writing the HTML content of articles into the database during the development of Django blog
- leetcode 1261. Find Elements in a Contaminated Binary Tree(python)
- [algorithm learning] 1486 Array XOR operation (Java / C / C + + / Python / go / trust)
- Understand Python's built-in function and add a print function yourself
- Python implements JS encryption algorithm in thousands of music websites
- leetcode 35. Search Insert Position(python)
- leetcode 1829. Maximum XOR for Each Query(python)
- [introduction to Python visualization]: 12 small examples of complete data visualization, taking you to play with visualization ~