In-depth understanding of Python's heapq built-in module introduction-Python Tutorial-php.cn

In-depth understanding of Python's heapq built-in module introduction

高洛峰

Release： 2017-03-15 14:19:27

Original

2681 people have browsed it

heapq is a built-in module of python. The source code is located in Lib/heapq.py. This module provides a heap-based prioritization algorithm.

The logical structure of the heap is a complete binary tree, and the value of the parent node in the binary tree is less than or equal to the value of all the child nodes of the node. This implementation can use heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2] (where k is the index, counting from 0) Formal expression, for a heap, the smallest element is the root element heap[0].

You can initialize the heap through list, or convert the known list into a heap through heapify in api Object.

Functions provided by heapqMethods

heapq.heappush(heap, item)

heapq.heappop(heap): Return the root node, which is the smallest element in the heap

heapq.heappushpop(heap, item): Add the item element to the heap and return the smallest element in the heap

heapq.heapify(x)

heapq.nlargest(n, iterable, key=None): Returns the n largest values in the enumerable object, and returns a result set list, the key is the result set Operation

heapq.nsmallest(n, iterable, key=None): Same as above but opposite

demo

1. Sort the list through heapq api

def heapsort(iterable):
    h = []

    for i in iterable:
        heapq.heappush(h, i)

    return [heapq.heappop(h) for i in range(len(h))]


s = [3, 5, 1, 2, 4, 6, 0, 1]
print(heapsort(s))

Copy after login

The output is as follows

 [0, 1, 1, 2, 3, 4, 5, 6]

Copy after login

2. Find the smallest price in the object list through key An item

portfolio = [
    {&#39;name&#39;: &#39;IBM&#39;, &#39;shares&#39;: 100, &#39;price&#39;: 91.1},
    {&#39;name&#39;: &#39;AAPL&#39;, &#39;shares&#39;: 50, &#39;price&#39;: 543.22},
    {&#39;name&#39;: &#39;FB&#39;, &#39;shares&#39;: 200, &#39;price&#39;: 21.09},
    {&#39;name&#39;: &#39;HPQ&#39;, &#39;shares&#39;: 35, &#39;price&#39;: 31.75},
    {&#39;name&#39;: &#39;YHOO&#39;, &#39;shares&#39;: 45, &#39;price&#39;: 16.35},
    {&#39;name&#39;: &#39;ACME&#39;, &#39;shares&#39;: 75, &#39;price&#39;: 115.65}
]
cheap = heapq.nsmallest(1, portfolio, key=lambda s: s[&#39;price&#39;])
print(cheap)

Copy after login

is output as follows

[{&#39;shares&#39;: 45, &#39;price&#39;: 16.35, &#39;name&#39;: &#39;YHOO&#39;}]

Copy after login

## extend

As mentioned above, heapq is the implementation of the minimum heap, so let's analyze how to convert the list into a minimum heap through the API in Python based on the source code of heapq (the keywords of the parent node are smaller than the left and right child nodes) )

can be divided into the following steps:

1. Starting from the last element with a child node, treat this parent node element and its child nodes as a unit

2. In the unit, swap the smaller element of the two child nodes with the parent node (there is no need to judge the size relationship between the parent node and the smallest child node). Through this step, you can change the unit to the smallest one. Heap unit

3. Through

while loop you can push smaller elements upward

def heapilize_list(x):
    n = len(x)
    # 获取存在子节点的节点 index 列表，并对每个节点单元进行最小堆处理
    for i in reversed(range(n // 2)):
        raiseup_node(x, i)

def put_down_node(heap, startpos, pos):
    current_item = heap[pos]
    # 判断单元中最小子节点与父节点的大小
    while pos > startpos:
        parent_pos = (pos - 1) >> 1
        parent_item = heap[parent_pos]

        if current_item < parent_item:
            heap[pos] = parent_item
            pos = parent_pos
            continue
        break

    heap[pos] = current_item

def raiseup_node(heap, pos):
    heap_len = len(heap)
    start_pos = pos
    current_item = heap[pos]
    left_child_pos = pos * 2 + 1

    while left_child_pos < heap_len:
        right_child_pos = left_child_pos + 1
        # 将这个单元中的最小子节点元素与父节点元素进行位置调换
        if right_child_pos < heap_len and not heap[left_child_pos] < heap[right_child_pos]:
            left_child_pos = right_child_pos
        heap[pos] = heap[left_child_pos]
        pos = left_child_pos
        left_child_pos = pos * 2 + 1
    heap[pos] = current_item
    put_down_node(heap, start_pos, pos)


p = [4, 6, 2, 10, 1]
heapilize_list(p)
print(p)

Copy after login

The output is as follows

[1, 6, 2, 10, 4]

Copy after login

The above is the detailed content of In-depth understanding of Python's heapq built-in module introduction. For more information, please follow other related articles on the PHP Chinese website!