Maison > Article > développement back-end > Compréhension approfondie de l'introduction du module intégré heapq de Python
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, heapq.nsmallest(n, iterable, key=None) : pareil que ci-dessus mais en face de
démo
1. Triez la liste via l'API heapqdef 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))Le résultat est le suivant
[0, 1, 1, 2, 3, 4, 5, 6]2. Rechercher la liste des objets via la clé Le plus petit article dans le prix
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 = heapq.nsmallest(1, portfolio, key=lambda s: s['price']) print(cheap)est affiché comme suit
[{'shares': 45, 'price': 16.35, 'name': 'YHOO'}]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 suivantdef 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)
[1, 6, 2, 10, 4]
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!