Heapq nlargest on Absolute Value but Get Sign Again
Heaps and priority queues are piddling-known just surprisingly useful data structures. For many problems that involve finding the all-time element in a dataset, they offering a solution that'southward piece of cake to use and highly effective. The Python heapq module is part of the standard library. It implements all the low-level heap operations equally well as some high-level common uses for heaps.
A priority queue is a powerful tool that tin solve problems as varied as writing an e-mail scheduler, finding the shortest path on a map, or merging log files. Programming is total of optimization problems in which the goal is to discover the best element. Priority queues and the functions in the Python heapq module can often assist with that.
In this tutorial, you'll acquire:
- What heaps and priority queues are and how they relate to each other
- What kinds of problems tin be solved using a heap
- How to use the Python
heapqmodule to solve those bug
This tutorial is for Pythonistas who are comfortable with lists, dicts, sets, and generators and are looking for more sophisticated information structures.
You lot tin follow along with the examples in this tutorial by downloading the source lawmaking from the link below:
What Are Heaps?
Heaps are concrete data structures, whereas priority queues are abstract data structures. An abstract data structure determines the interface, while a concrete data structure defines the implementation.
Heaps are commonly used to implement priority queues. They're the most popular concrete data structure for implementing the priority queue abstract information structure.
Concrete data structures also specify performance guarantees. Performance guarantees define the relationship between the size of the structure and the fourth dimension operations take. Understanding those guarantees allows you to predict how much time the program will take as the size of its inputs change.
Data Structures, Heaps, and Priority Queues
Abstract data structures specify operations and the relationships between them. The priority queue abstruse information structure, for example, supports iii operations:
- is_empty checks whether the queue is empty.
- add_element adds an chemical element to the queue.
- pop_element pops the element with the highest priority.
Priority queues are commonly used for optimizing job execution, in which the goal is to work on the task with the highest priority. After a job is completed, its priority is lowered, and information technology's returned to the queue.
There are ii different conventions for determining the priority of an element:
- The largest element has the highest priority.
- The smallest chemical element has the highest priority.
These two conventions are equivalent because you tin can always reverse the effective order. For example, if your elements consist of numbers, then using negative numbers will flip the conventions around.
The Python heapq module uses the 2d convention, which is mostly the more common of the two. Under this convention, the smallest element has the highest priority. This might audio surprising, merely information technology's oft quite useful. In the real-life examples you'll run across after, this convention will simplify your code.
Concrete information structures implement the operations defined in an abstract data construction and farther specify performance guarantees.
The heap implementation of the priority queue guarantees that both pushing (adding) and popping (removing) elements are logarithmic time operations. This means that the time it takes to do push and popular is proportional to the base-two logarithm of the number of elements.
Logarithms grow slowly. The base-2 logarithm of fifteen is about four, while the base of operations-2 logarithm of a trillion is nigh forty. This means that if an algorithm is fast enough on fifteen elements, and so information technology'southward going to be only 10 times slower on a trillion elements and will probably withal be fast enough.
In whatever give-and-take of performance, the biggest caveat is that these abstruse considerations are less meaningful than actually measuring a concrete program and learning where the bottlenecks are. General performance guarantees are withal important for making useful predictions about program beliefs, but those predictions should be confirmed.
Implementation of Heaps
A heap implements a priority queue every bit a complete binary tree. In a binary tree, each node will take at most two children. In a complete binary tree, all levels except possibly the deepest one are total at all times. If the deepest level is incomplete, then information technology will have the nodes as far to the left equally possible.
The completeness property means that the depth of the tree is the base-2 logarithm of the number of elements, rounded upward. Here'southward an case of a complete binary tree:
In this particular example, all levels are consummate. Each node except for the deepest ones has exactly 2 children. At that place are a full of 7 nodes in three levels. Three is the base-2 logarithm of 7, rounded up.
The single node at the base of operations level is called the root node. It might seem weird to call the node at the peak of the tree the root, but this is the common convention in programming and informatics.
The functioning guarantees in a heap depend on how elements percolate upwardly and down the tree. The practical result of this is that the number of comparisons in a heap is the base-2 logarithm of the size of the tree.
In a heap tree, the value in a node is always smaller than both of its children. This is called the heap belongings. This is unlike from a binary search tree, in which but the left node will be smaller than the value of its parent.
The algorithms for both pushing and popping rely on temporarily violating the heap property, then fixing the heap holding through comparisons and replacements upward or downwardly a single branch.
For example, to button an element onto a heap, Python adds the new node to the next open slot. If the bottom layer isn't full, and so the node is added to the side by side open slot at the bottom. Otherwise, a new level is created and then the element is added to the new lesser layer.
Once the node is added, Python compares it to its parent. If the heap property is violated, then the node and its parent are switched, and the check begins once more at the parent. This continues until the heap property holds or the root has been reached.
Similarly, when popping the smallest element, Python knows that, because of the heap property, the element is at the root of the tree. Information technology replaces the element with the last chemical element at the deepest layer so checks if the heap holding is violated down the branch.
Uses of Priority Queues
A priority queue, and a heap as an implementation of a priority queue, is useful for programs that involve finding an element that is extreme in some way. For example, you tin can utilise a priority queue for any of the following tasks:
- Getting the 3 nearly popular blog posts from hit data
- Finding the fastest way to get from one betoken to the other
- Predicting which motorcoach will exist the first to go far at a station based on inflow frequency
Another task for which y'all could apply a priority queue is scheduling emails. Imagine a system that has several kinds of emails, each of which needs to exist sent at a sure frequency. One kind of e-mail needs to go out every xv minutes, and another needs to be sent every forty minutes.
A scheduler could add both types of email to the queue with a timestamp indicating when the electronic mail next needs to be sent. So the scheduler could await at the chemical element with the smallest timestamp—indicating that information technology's side by side in line to exist sent—and summate how long to sleep before sending.
When the scheduler wakes up, information technology would procedure the relevant electronic mail, take the email out of the priority queue, calculate the side by side timestamp, and put the e-mail back in the queue at the correct location.
Heaps as Lists in the Python heapq Module
Although you saw the heap described earlier as a tree, it's important to retrieve that it's a complete binary tree. Completeness means that it's e'er possible to tell how many elements are at each layer except the concluding ane. Because of this, heaps tin be implemented as a listing. This is what the Python heapq module does.
There are three rules that determine the relationship betwixt the element at the index thousand and its surrounding elements:
- Its first child is at
ii*1000 + 1. - Its 2d child is at
2*k + ii. - Its parent is at
(1000 - one) // 2.
The rules higher up tell you how to visualize a list every bit a complete binary tree. Go on in heed that an element always has a parent, but some elements don't accept children. If 2*k is beyond the finish of the list, then the element doesn't have any children. If 2*chiliad + 1 is a valid alphabetize but 2*grand + 2 is not, then the chemical element has only ane kid.
The heap property means that if h is a heap, then the following will never exist Imitation:
h [ k ] <= h [ 2 * thou + 1 ] and h [ k ] <= h [ 2 * chiliad + 2 ] It might enhance an IndexError if any of the indices is across the length of the listing, but information technology will never be False.
In other words, an element must e'er be smaller than the elements that are at twice its index plus 1 and twice its alphabetize plus two.
Hither's a visual of a list that satisfies the heap property:
The arrows become from chemical element k to elements 2*k + i and 2*k + ii. For case, the first element in a Python list has the index 0, and so its two arrows point at indices 1 and 2. Discover how the arrows ever become from a smaller value to a bigger value. This is how you tin check that the list satisfies the heap property.
Basic Operations
The Python heapq module implements heap operations on lists. Unlike many other modules, it does not define a custom class. The Python heapq module has functions that work on lists directly.
Usually, as in the e-mail example above, elements will be inserted into a heap one by one, starting with an empty heap. Nevertheless, if there'south already a list of elements that needs to be a heap, then the Python heapq module includes heapify() for turning a listing into a valid heap.
The post-obit code uses heapify() to turn a into a heap:
>>>
>>> import heapq >>> a = [ iii , 5 , 1 , 2 , half dozen , 8 , 7 ] >>> heapq . heapify ( a ) >>> a [1, 2, 3, five, vi, 8, 7] You tin check that even though seven comes after 8, the list a all the same obeys the heap property. For example, a[2], which is 3, is less than a[2*2 + 2], which is 7.
Equally you can meet, heapify() modifies the listing in place merely doesn't sort it. A heap doesn't have to exist sorted to satisfy the heap property. Still, since every sorted listing does satisfy the heap property, running heapify() on a sorted list won't alter the order of elements in the list.
The other basic operations in the Python heapq module assume that the list is already a heap. It'due south useful to annotation that an empty list or a list of length one will always be a heap.
Since the root of the tree is the first element, you don't need a dedicated office to read the smallest chemical element nondestructively. The first element, a[0], will always be the smallest element.
To pop the smallest element while preserving the heap holding, the Python heapq module defines heappop().
Here's how to use heappop() to pop an element:
>>>
>>> import heapq >>> a = [ one , ii , three , 5 , 6 , 8 , 7 ] >>> heapq . heappop ( a ) one >>> a [2, 5, 3, seven, half dozen, viii] The function returns the beginning element, i, and preserves the heap property on a. For example, a[ane] is five and a[1*2 + 2] is six.
The Python heapq module besides includes heappush() for pushing an element to the heap while preserving the heap property.
The following example shows pushing a value to a heap:
>>>
>>> import heapq >>> a = [ ii , five , iii , 7 , half dozen , 8 ] >>> heapq . heappush ( a , iv ) >>> a [2, five, 3, 7, 6, viii, iv] >>> heapq . heappop ( a ) 2 >>> heapq . heappop ( a ) 3 >>> heapq . heappop ( a ) four Afterwards pushing 4 to the heap, y'all pop three elements from information technology. Since 2 and 3 were already in the heap and are smaller than 4, they're popped start.
The Python heapq module also defines two more operations:
-
heapreplace()is equivalent toheappop()followed byheappush(). -
heappushpop()is equivalent toheappush()followed pastheappop().
These are useful in some algorithms since they're more efficient than doing the two operations separately.
A High-Level Operation
Since priority queues are so often used to merge sorted sequences, the Python heapq module has a ready-made function, merge(), for using heaps to merge several iterables. merge() assumes its input iterables are already sorted and returns an iterator, not a listing.
As an instance of using merge(), here'due south an implementation of the electronic mail scheduler described earlier:
import datetime import heapq def electronic mail ( frequency , details ): electric current = datetime . datetime . now () while True : current += frequency yield current , details fast_email = email ( datetime . timedelta ( minutes = 15 ), "fast e-mail" ) slow_email = email ( datetime . timedelta ( minutes = forty ), "irksome e-mail" ) unified = heapq . merge ( fast_email , slow_email ) The inputs to merge() in this case are infinite generators. The return value assigned to the variable unified is also an infinite iterator. This iterator will yield the emails to exist sent in the society of the futurity timestamps.
To debug and ostend that the code is merging correctly, you tin can impress the first 10 emails to be sent:
>>>
>>> for _ in range ( 10 ): ... print ( next ( chemical element )) (datetime.datetime(2020, iv, 12, 21, 27, 20, 305358), 'fast e-mail') (datetime.datetime(2020, iv, 12, 21, 42, twenty, 305358), 'fast e-mail') (datetime.datetime(2020, four, 12, 21, 52, twenty, 305360), 'deadening e-mail') (datetime.datetime(2020, 4, 12, 21, 57, twenty, 305358), 'fast electronic mail') (datetime.datetime(2020, 4, 12, 22, 12, twenty, 305358), 'fast email') (datetime.datetime(2020, iv, 12, 22, 27, 20, 305358), 'fast electronic mail') (datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'deadening electronic mail') (datetime.datetime(2020, 4, 12, 22, 42, xx, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast e-mail') (datetime.datetime(2020, 4, 12, 23, 12, twenty, 305358), 'fast email') Observe how the fast email is scheduled every 15 minutes, the boring email is scheduled every 40, and the emails are properly interleaved and so that they're bundled in the order of their timestamps.
merge() doesn't read all the input, but rather it works dynamically. Even though both inputs are infinite iterators, printing the kickoff ten items finishes quickly.
In a similar mode, when used to merge sorted sequences like log file lines arranged by timestamp, even if the logs are big, this will take reasonable amounts of retention.
Problems Heaps Can Solve
As you saw above, heaps are good for incrementally merging sorted sequences. 2 applications for heaps that you lot've already considered are scheduling periodic tasks and merging log files. However, there are many more applications.
Heaps can also help identify the height northward or bottom n things. The Python heapq module has high-level functions that implement this behavior.
For example, this code gets every bit input the times from the women's 100 meters last at the 2022 Summer Olympics and prints the medalists, or top 3 finishers:
>>>
>>> import heapq >>> results = """ \ ... Christania Williams 11.eighty ... Marie-Josee Ta Lou 10.86 ... Elaine Thompson 10.71 ... Tori Bowie 10.83 ... Shelly-Ann Fraser-Pryce 10.86 ... English Gardner 10.94 ... Michelle-Lee Ahye ten.92 ... Dafne Schippers ten.90 ... """ >>> top_3 = heapq . nsmallest ( ... 3 , results . splitlines (), key = lambda x : bladder ( x . carve up ()[ - 1 ]) ... ) >>> print ( " \n " . join ( top_3 )) Elaine Thompson 10.71 Tori Bowie 10.83 Marie-Josee Ta Lou x.86 This lawmaking uses nsmallest() from the Python heapq module. nsmallest() returns the smallest elements in an iterable and accepts three arguments:
-
northwardindicates how many elements to return. -
iterableidentifies the elements or dataset to compare. -
keyis a callable role that determines how elements are compared.
Here, the central function splits the line by whitespace, takes the last element, and converts it to a floating-point number. This means the code will sort the lines past running time and return the three lines with the smallest running times. These correspond to the three fastest runners, which gives you the golden, silver, and statuary medal winners.
The Python heapq module also includes nlargest(), which has similar parameters and returns the largest elements. This would be useful if you wanted to go the medalists from the javelin throw competition, in which the goal is to throw the javelin as far as possible.
How to Identify Problems
A heap, as an implementation of a priority queue, is a good tool for solving problems that involve extremes, similar the most or least of a given metric.
There are other words that indicate a heap might be useful:
- Largest
- Smallest
- Biggest
- Smallest
- Best
- Worst
- Tiptop
- Bottom
- Maximum
- Minimum
- Optimal
Whenever a trouble statement indicates that you're looking for some extreme element, information technology'southward worthwhile to recollect about whether a priority queue would be useful.
Sometimes the priority queue will exist simply part of the solution, and the rest volition be some variant on dynamic programming. This is the case with the full instance that you'll see in the next department. Dynamic programming and priority queues are oft useful together.
Instance: Finding Paths
The post-obit example serves as a realistic employ example for the Python heapq module. The case will utilise a classic algorithm that, as ane part of it, requires a heap. Y'all tin can download the source code used in the examples by clicking the link below:
Imagine a robot that needs to navigate a two-dimensional maze. The robot needs to go from the origin, positioned at the peak-left corner, to the destination at the bottom-right corner. The robot has a map of the maze in its memory, then it can plan out the whole path before setting out.
The goal is to have the robot finish the maze every bit quickly as possible.
Our algorithm is a variant of Dijkstra'due south algorithm. There are three data structures that are kept and updated throughout the algorithm:
-
tentativeis a map of a tentative path from the origin to a position,pos. The path is called tentative considering it's the shortest known path, simply information technology might be improved upon. -
certainis set of points for which the path thattentativemaps is sure to exist the shortest possible path. -
candidatesis a heap of positions that have a path. The sorting central of the heap is the length of the path.
At each step, you perform upward to four actions:
-
Popular a candidate from
candidates. -
Add the candidate to the
certaingear up. If the candidate is already a member of thecertainset, so skip next two actions. -
Find the shortest known path to the current candidate.
-
For each of the current candidate's immediate neighbors, see if going through the candidate gives a shorter path than the current
tentativepath. If and so, and so update thetentativepath and thecandidatesheap with this new path.
The steps are run in a loop until the destination is added to the certain set. When the destination is in the certain set, you're done. The output of the algorithm is the tentative path to the destination, which is now certain to exist the shortest possible path.
Top-Level Code
Now that you understand the algorithm, information technology's time to write code to implement it. Before implementing the algorithm itself, it'southward useful to write some back up lawmaking.
First, you need to import the Python heapq module:
You'll employ the functions from the Python heapq module to maintain a heap that will aid yous find the position with the shortest known path at each iteration.
The side by side step is to ascertain the map as a variable in the lawmaking:
map = """ \ .......X.. .......X.. ....XXXX.. .......... .......... """ The map is a triple-quoted string that shows the area in which the robot tin move as well as any obstacles.
Though a more realistic scenario would accept you reading the map from a file, for didactics purposes it'southward easier to define a variable in the code using this simple map. The code will work on any map, but information technology'south easier to sympathise and debug on a simple map.
This map is optimized to exist easy to sympathize for a human being reader of the code. The dot (.) is light plenty that information technology looks empty, but it has the advantage of showing the dimensions of the immune area. The X positions mark obstacles that the robot tin't become through.
Back up Code
The start part will convert the map to something easier to parse in code. parse_map() gets a map and analyzes it:
def parse_map ( map ): lines = map . splitlines () origin = 0 , 0 destination = len ( lines [ - 1 ]) - 1 , len ( lines ) - 1 render lines , origin , destination The function takes a map and returns a tuple of iii elements:
- A listing of
lines - The
origin - The
destination
This allows the rest of the code to work on data structures designed for computers, not for humans' power to visually scan.
The list of lines tin be indexed by (x, y) coordinates. The expression lines[y][x] returns the value of the position equally one of two characters:
- A dot (
".") indicates the position is an empty space. - The letter
"X"indicates the position is an obstacle.
This will be useful when you want to discover which positions the robot can occupy.
The function is_valid() calculates whether a given (10, y) position is valid:
def is_valid ( lines , position ): x , y = position if not ( 0 <= y < len ( lines ) and 0 <= x < len ( lines [ y ])): render False if lines [ y ][ x ] == "X" : return Fake return Truthful This office takes two arguments:
-
linesis the map as a list of lines. -
positionis the position to check equally a two-tuple of integers indicating the(x, y)coordinates.
To be valid, a position has to be inside the boundaries of the map and non an obstacle.
The part checks that y is valid by checking the length of the lines list. The office next checks that x is valid past making sure it'south within lines[y]. Finally, now that you know both coordinates are inside the map, the code checks that they're non an obstruction past looking at the character in this position and comparing the character to "X".
Another useful helper is get_neighbors(), which finds all the neighbors of a position:
def get_neighbors ( lines , current ): x , y = current for dx in [ - i , 0 , 1 ]: for dy in [ - 1 , 0 , 1 ]: if dx == 0 and dy == 0 : continue position = ten + dx , y + dy if is_valid ( lines , position ): yield position The function returns all the valid positions surrounding the current position.
get_neighbors() is careful to avoid identifying a position every bit its ain neighbor, simply it does allow diagonal neighbors. This is why at to the lowest degree one of dx and dy must not be cypher, simply it's okay for both of them to exist non-zero.
The final helper part is get_shorter_paths(), which finds shorter paths:
def get_shorter_paths ( tentative , positions , through ): path = tentative [ through ] + [ through ] for position in positions : if position in tentative and len ( tentative [ position ]) <= len ( path ): proceed yield position , path get_shorter_paths() yields positions for which the path that has through equally its final step is shorter than the current known path.
get_shorter_paths() has 3 parameters:
-
tentativeis a lexicon mapping a position to the shortest known path. -
positionsis an iterable of positions to which you lot want to shorten the path. -
throughis the position through which, perhaps, a shorter path to thepositionscan exist found.
The assumption is that all elements in positions can exist reached in 1 step from through.
The function get_shorter_paths() checks if using through equally the last footstep will make a amend path for each position. If there'south no known path to a position, then any path is shorter. If in that location is a known path, then yous only yield the new path if its length is shorter. In society to make the API of get_shorter_paths() easier to use, part of the yield is also the shorter path.
All helper functions were written to be pure functions, pregnant they don't alter whatsoever information structures and but return values. This makes it easier to follow the cadre algorithm, which does all the data construction updates.
Core Algorithm Code
To recap, you lot're looking for the shortest path between the origin and the destination.
You keep three pieces of information:
-
certainis the set of certain positions. -
candidatesis the heap of candidates. -
tentativeis a lexicon mapping nodes to the current shortest known path.
A position is in certain if you can be sure that the shortest known path is the shortest possible path. If the destination is in the certain set, and then the shortest known path to the destination is unquestionably the shortest possible path, and you tin can return this path.
The heap of candidates is organized past the length of the shortest known path and is managed with the help of the functions in the Python heapq module.
At each footstep, yous look at the candidate with the shortest known path. This is where the heap is beingness popped with heappop(). There is no shorter path to this candidate—all other paths get through some other node in candidates, and all of these are longer. Because of that, the current candidate can exist marked certain.
You then look at all neighbors that have not been visited, and if going through the current node is an improvement, so you lot add them to the candidates heap using heappush().
The function find_path() implements this algorithm:
1 def find_path ( map ): 2 lines , origin , destination = parse_map ( map ) iii tentative = { origin : []} four candidates = [( 0 , origin )] five certain = gear up () 6 while destination not in sure and len ( candidates ) > 0 : 7 _ignored , current = heapq . heappop ( candidates ) 8 if current in certain : nine go along x certain . add ( current ) eleven neighbors = set ( get_neighbors ( lines , electric current )) - certain 12 shorter = get_shorter_paths ( tentative , neighbors , current ) 13 for neighbour , path in shorter : fourteen tentative [ neighbor ] = path 15 heapq . heappush ( candidates , ( len ( path ), neighbour )) xvi if destination in tentative : 17 return tentative [ destination ] + [ destination ] 18 else : 19 enhance ValueError ( "no path" ) find_path() receives a map every bit a cord and returns the path from the origin to the destination equally a list of positions.
This function is a little long and complicated, so let's walk through it one bit at a time:
-
Lines two through 5 gear up the variables that the loop will expect at and update. Yous already know a path from the origin to itself, which is the empty path, of length 0.
-
Line six defines the loop's termination status. If there are no
candidates, then no paths tin can exist shortened. Ifdestinationis insure, then the path todestinationcan't be made shorter. -
Lines 7 through 10 go a candidate using
heappop(), skip the loop if it's already incertain, and otherwise add the candidate tosure. This makes sure every candidate will be processed by the loop at most once. -
Lines eleven through 15 utilise
get_neighbors()andget_shorter_paths()to observe shorter paths to neighboring positions and update thetentativedictionary andcandidatesheap. -
Lines xvi through 19 deal with returning the correct result. If a path was found, then the role volition return information technology. Although calculating the paths without the terminal position made implementing the algorithm simpler, it's a nicer API to return information technology with the destination. If no path is establish, then an exception is raised.
Breaking the function into divide sections lets you understand it i part at a time.
Visualization Code
If the algorithm was actually used by a robot, then the robot would probably perform better with a list of positions that it should travel through. However, to make the result better looking to humans, information technology would be nicer to visualize them.
show_path() draws a path on a map:
def show_path ( path , map ): lines = map . splitlines () for x , y in path : lines [ y ] = lines [ y ][: x ] + "@" + lines [ y ][ ten + 1 :] return " \n " . join ( lines ) + " \northward " The part takes the path and map as parameters. It returns a new map with the path indicated by the at symbol ("@").
Running the Lawmaking
Finally, you need to call the functions. This tin be done from the Python interactive interpreter.
The following code volition run the algorithm and show a pretty output:
>>>
>>> path = find_path ( map ) >>> print ( show_path ( path , map )) @@.....10.. ..@....X.. ...@XXXX.. ....@@@@@. .........@ Kickoff you go the shortest path from find_path(). Then you pass it to show_path() to render a map with the path marked on it. Finally, you print() the map to the standard output.
The path moves one step to the right, then a few diagonal steps toward the bottom-right, then several more steps to the right, and it finally finishes with a diagonal step to the bottom-right.
Congratulations! Yous've solved a problem using the Python heapq module.
These kinds of pathfinding problems, solvable past a combination of dynamic programming and priority queues, are common in job interviews and programming challenges. For case, the 2022 Appearance of Code included a problem that could be solved with the techniques described here.
Conclusion
You now know what the heap and priority queue information structures are and what kinds of problems they're useful in solving. You learned how to utilize the Python heapq module to employ Python lists every bit heaps. Yous also learned how to use the loftier-level operations in the Python heapq module, like merge(), which utilize a heap internally.
In this tutorial, you've learned how to:
- Employ the low-level functions in the Python
heapqmodule to solve problems that need a heap or a priority queue - Use the high-level functions in the Python
heapqmodule for merging sorted iterables or finding the largest or smallest elements in an iterable - Recognize problems that heaps and priority queues can help solve
- Predict the performance of code that uses heaps
With your knowledge of heaps and the Python heapq module, y'all tin now solve many problems in which the solution depends on finding the smallest or largest element. To follow forth with the examples you saw in this tutorial, yous can download the source lawmaking from the link below:
Source: https://realpython.com/python-heapq-module/
Post a Comment for "Heapq nlargest on Absolute Value but Get Sign Again"