Compréhension approfondie de l'introduction du module intégré heapq de Python-Tutoriel Python-php.cn

Compréhension approfondie de l'introduction du module intégré heapq de Python

高洛峰

Libérer： 2017-03-15 14:19:27

original

2654 Les gens l'ont consulté

heapq est un module intégré de python Le code source se trouve dans Lib/heapq.py. Ce module fournit un algorithme de priorisation basé sur le tas.

La structure logique du tas est un arbre binaire complet, et la valeur du nœud parent dans l'arbre binaire est inférieure ou égale à la valeur de tous les nœuds enfants du nœud. Cette implémentation peut être implémentée sous la forme de heap[k] <= heap[2k 1] et heap[k] <= heap[2k 2] (où k est index , en comptant à partir de 0) , pour un tas, le plus petit élément est l'élément racine tas[0].

Vous pouvez initialiser le tas via list, ou convertir la liste connue en tas ify dans api >Object.

Heapq fournit la fonction méthode

heapq.heappush(heap, item)

heapq.heappop(heap) : Renvoie le nœud racine, c'est-à-dire le plus petit élément du tas

heapq.heappushpop(heap, item) : ajoute l'élément item au tas et renvoie le plus petit élément du tas

heapq.heapify(x)

heapq.nlargest(n, iterable,

key=None) : renvoie les n plus grandes valeurs de l'objet énumérable et renvoie une liste de jeux de résultats, la clé est l'ensemble de résultats Opération de

heapq.nsm

allest(n, iterable, key=None) : pareil que ci-dessus mais en face de

démo

1. Triez la liste via l'API heapq

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))

Copier après la connexion

Le résultat est le suivant

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

Copier après la connexion

2. Rechercher la liste des objets via la clé Le plus petit article dans le prix

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)

Copier après la connexion

est affiché comme suit

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

Copier après la connexion

extend

Comme mentionné ci-dessus, heapq est l'implémentation du tas minimum, analysons donc en fonction du code source de heapq comment convertir la liste en un tas minimum (le mot-clé du nœud parent est plus petit que les nœuds enfants gauche et droit)

peut être divisé en les étapes suivantes :

1. élément avec des nœuds enfants, ajoutez cet élément de nœud parent et ses nœuds enfants Traitez-le comme une unité

2 Dans l'unité, échangez le plus petit élément des deux nœuds enfants avec le nœud parent (il n'est pas nécessaire de le faire). juger de la relation de taille entre le nœud parent et le plus petit nœud enfant). Grâce à cette étape, vous pouvez changer cette unité en une unité de tas minimale

via

while boucle <🎜. > vous pouvez pousser des éléments plus petits vers le haut

Le résultat est le suivant

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)

Copier après la connexion