I. Creating a Heap
There are two ways to create a heap in heapq, one is to use an empty list and add the values to the heap using the () function, and the other is to convert the list into a heap structure using the (list) function.
import heapq # The first """ function definition： (heap, item) - Push the value item onto the heap, maintaining the heap invariant. (heap) - Pop and return the smallest item from the heap, maintaining the heap invariant. If the heap is empty, IndexError is raised. To access the smallest item without popping it, use heap[0]. """ nums = [2, 3, 5, 1, 54, 23, 132] heap = [] for num in nums: (heap, num) # Join the pile print(heap[0]) # If you just want to get the minimum value instead of a popup, use heap[0] print([(heap) for _ in range(len(nums))]) # Heap sort results # out: [1, 2, 3, 5, 23, 54, 132] # The second nums = [2, 3, 5, 1, 54, 23, 132] (nums) print([(heap) for _ in range(len(nums))]) # Heap sort results # out: [1, 2, 3, 5, 23, 54, 132]
The heapq module also has a(*iterables)method that combines multiple sorted sequences into a single sorted sequence, returning an iterator of the sorted values.
alikesorted((*iterables)), but the return is iterable.
""" function definition： (*iterables) - Merge multiple sorted inputs into a single sorted output (for example, merge timestamped entries from multiple log files). Returns an iterator over the sorted values. - Similar to sorted((*iterables)) but returns an iterable, does not pull the data into memory all at once, and assumes that each of the input streams is already sorted (smallest to largest). """ import heapq num1 = [32, 3, 5, 34, 54, 23, 132] num2 = [23, 2, 12, 656, 324, 23, 54] num1 = sorted(num1) num2 = sorted(num2) res = (num1, num2) print(list(res))
II. Access to the contents of the heap
Once the heap is created, you can pop the minimum value in the heap with the `() function.
import heapq nums = [2, 43, 45, 23, 12] (nums) print((nums)) # out: 2 # If all heap-sorted elements are needed result = [(nums) for _ in range(len(nums))] print(result) # out: [12, 23, 43, 45]
If you need to remove the smallest element of the heap and add an element, you can use the()function (math.)
import heapq nums = [1, 2, 4, 5, 3] (nums) (nums, 23) print([(nums) for _ in range(len(nums))]) # out: [2, 3, 4, 5, 23]
III. Getting the maximum or minimum value of the heap
If you need to get the maximum or minimum range value in the heap, you can use the()maybe()function (math.)
""" function definition： (n, iterable[, key])¶ - Return a list with the n largest elements from the dataset defined by iterable. - key if provided, specifies a function of one argument that is used to extract a comparison key from each element in the iterable: key= - Equivalent to: sorted(iterable, key=key, reverse=True)[:n] """ import heapq nums = [1, 3, 4, 5, 2] print((3, nums)) print((3, nums)) """ Output: [5, 4, 3] [1, 2, 3] """
Both functions also accept a key parameter for dict or other data structure types using the
import heapq
from pprint import pprint
portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'name': 'AAPL', 'shares': 50, 'price': 543.22},
{'name': 'FB', 'shares': 200, 'price': 21.09},
{'name': 'HPQ', 'shares': 35, 'price': 31.75},
{'name': 'YHOO', 'shares': 45, 'price': 16.35},
{'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = (3, portfolio, key=lambda s: s['price'])
expensive = (3, portfolio, key=lambda s: s['price'])
pprint(cheap)
pprint(expensive)
"""
exports：
[{'name': 'YHOO', 'price': 16.35, 'shares': 45},
{'name': 'FB', 'price': 21.09, 'shares': 200},
{'name': 'HPQ', 'price': 31.75, 'shares': 35}]
[{'name': 'AAPL', 'price': 543.22, 'shares': 50},
{'name': 'ACME', 'price': 115.65, 'shares': 75},
{'name': 'IBM', 'price': 91.1, 'shares': 100}]
"""iv. heapq applications
Implement the heap heap sort algorithm:
>>> 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]) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
The algorithm andsorted(iterable)Similar, but it is unstable.
The value of the heap can be of tuple type, which enables sorting of elements with weights.
>>> 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')
to this article on the implementation of python heapq heap row algorithm is introduced to this article, more related python heapq heap content please search for my previous articles or continue to browse the following related articles I hope you will support me in the future!