heapq heap queue algorithm
This module provides the implementation of the heap queue algorithm, also known asPriority queuealgorithm.
The heap is a binary tree, and the value of each parent node ≤ \le ≤ values of all child nodes. Implemented with an array: count from zero, for all k, there are heap[k] ≤ \le ≤ heap[2k+1] and heap[k] ≤ \le ≤ heap[2k+2]. The smallest element is always at the root node: heap[0].
(x) # Convert list x to heap, in place, in linear time.(heap, item) # Add the value of item to the heap to keep the heap invariant.(heap) #Popt out and return the smallest element of heap, keeping the heap invariant. If the heap is empty, throw an IndexError. Using heap[0] , you can access only the smallest element without popping it.(heap, item) #Put the item into the heap, then pop up and return the smallest element of the heap. This combination operation is more efficient than calling heappush() first and then calling heappop().(heap, item) #Pop up and return heap The smallest one，At the same time, new item。The size of the heap remains unchanged。If the heap is empty, it will be raised IndexError。
This single-step operation is more efficient than heappop() plus heappush() and is more suitable when using fixed-sized heaps. The pop/push combination always returns an element from the heap and replaces it with an item.
The returned value may be larger than the item added. If you don't want this, consider using heappushpop() instead. Its push/pop combination returns the smaller of the two values, leaving the larger value in the heap.
The module also provides three heap-based general functional functions.
(*iterables, key=None, reverse=False) #Combine multiple sorted inputs into one sorted output（For example，Merge timestamped entries from multiple log files）。 Returns the sorted value iterator。
Similar to sorted((*iterables)) but returns an iterable object that does not put all the data into memory at once and assumes that each input stream is sorted (from small to large).
Have two optional parameters, both of which must be specified as keyword parameters.
key Specifies a key function with a single parameter to extract the comparison key from each input element. The default value is None (directly compare elements).
reverse is a boolean value. If set to True, the input elements are merged in reverse order of comparison results. To achieve a similar behavior to sorted((*iterables), reverse=True), all iterable objects must be sorted from large to small.
(n, iterable, key=None) #Returns a list of the first n largest elements from the dataset defined by iterable. If key is provided it should specify a single parameter function to extract the comparison key from each element of iterable (for example, key=). Equivalent to: sorted(iterable, key=key, reverse=True)[:n].(n, iterable, key=None) #from iterable Before returning to the defined dataset n List of smallest elements。 If provided key Then it should specify a single parameter function，用于from iterable Extract the comparison key from each element (For example key=)。 Equivalent to: sorted(iterable, key=key)[:n]。
The last two functions perform best when the n value is small. For larger values, using the sorted() function is more efficient. Additionally, using the built-in min() and max() functions is more efficient when n==1. If you need to reuse these functions, consider turning the iterable object into a real heap.
1. Heapq creates a heap
import heapq
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heap = []
for num in array:
(heap, num)
print("array:", array)
print("heap: ", heap)
(array)
print("array:", array)
# array: [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
# heap: [5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
# array: [5, 7, 21, 10, 17, 24, 27, 45, 15, 30, 36, 50]There are two ways to create a heap in heapq:
- heappush(heap, num), first create an empty heap, and then add data to the heap one by one.
- heapify(array), directly adjust the data list into a small top heap.
2. Heap sorting
This can be done by pushing all values into the heap and popping up a minimum value item at a time.
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])This is similar to sorted(iterable), but unlike sorted(), this implementation isUnstable。
The heap element can be a tuple. This is suitable for the situation where comparison values (such as task priority) are assigned to the tracked master record:
h = [] heappush(h, (5, 'write code')) heappush(h, (7, 'release product')) heappush(h, (1, 'write spec')) heappush(h, (3, 'create tests')) heappop(h) (1, 'write spec')
First add the data in the list to be sorted to the heap, construct a small top heap, print the first data, and confirm that it is the minimum value. Then take out the value at the top of the heap in turn and add it to a new list until the data in the heap is taken, and the new list is the sorted list.
heappop(heap), the data on the top of the heap is out of the heap and the remaining data in the heap is constructed into a new small top heap.
3. Get the minimum or maximum value in the heap
array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] (array) print((2, array)) print((3, array))
4. Use heapq to merge two ordered lists
array_a = [10, 7, 15, 8]
array_b = [17, 3, 8, 20, 13]
array_merge = (sorted(array_a), sorted(array_b))
print("merge result:", list(array_merge))5. Heapq method to replace data
array_c = [10, 7, 15, 8]
(array_c)
print("before:", array_c)
# push first and popitem = (array_c, 5)
print("after: ", array_c)
print(item)
array_d = [10, 7, 15, 8]
(array_d)
print("before:", array_d)
# pop first and pushitem = (array_d, 5)
print("after: ", array_d)
print(item)This is the end of this article about the analysis of heapq module in Python. For more related heapq module analysis content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!