Comment utiliser le module heapq en Python

Le module heapq fournit des algorithmes de tas. heapq est une structure de données arborescente dans laquelle les nœuds enfants et les nœuds parents sont triés. Ce module fournit heap[k]

Imprimer le type heapq

import math 
import random
from cStringIO import StringIO

def show_tree(tree, total_width=36, fill=' '):
   output = StringIO()
   last_row = -1
   for i, n in enumerate(tree):
     if i:
       row = int(math.floor(math.log(i+1, 2)))
     else:
       row = 0
     if row != last_row:
       output.write('\n')
     columns = 2**row
     col_width = int(math.floor((total_width * 1.0) / columns))
     output.write(str(n).center(col_width, fill))
     last_row = row
   print output.getvalue()
   print '-' * total_width
   print 
   return

data = random.sample(range(1,8), 7)
print 'data: ', data
show_tree(data)

Résultat de l'impression

data: [3, 2, 6, 5, 4, 7, 1]

     3           
  2      6      
5    4  7     1   
-------------------------
heapq.heappush(heap, item)

Poussez un élément dans le tas et modifiez le code ci-dessus

heap = []
data = random.sample(range(1,8), 7)
print 'data: ', data

for i in data:
  print 'add %3d:' % i
  heapq.heappush(heap, i)
  show_tree(heap)

Imprimez le résultat

data: [6, 1, 5, 4, 3, 7, 2]
add  6:
         6         
 ------------------------------------
add  1:
      1 
   6         
------------------------------------
add  5:
      1 
   6       5       
------------------------------------
add  4:
        1 
    4       5       
  6
------------------------------------
add  3:
        1 
    3       5       
  6    4
------------------------------------
add  7:
        1 
    3        5       
  6    4    7
------------------------------------
add  2:
        1 
    3        2       
  6    4    7    5
------------------------------------

D'après les résultats, on peut comprendre que les éléments du nœud enfant sont plus grands que les éléments du nœud parent. Les nœuds frères et sœurs ne seront pas triés.

heapq.heapify(list)

Convertissez le type de liste en tas et réorganisez la liste en temps linéaire.

print 'data: ', data
heapq.heapify(data)
print 'data: ', data

show_tree(data)

Imprimer le résultat

data: [2, 7, 4, 3, 6, 5, 1]
data: [1, 3, 2, 7, 6, 5, 4]

      1         
   3         2     
7    6    5    4  
------------------------------------
heapq.heappop(heap)

Supprimer et renvoyer la plus petite valeur dans le tas Les éléments sont triés via heapify() et heappop().

data = random.sample(range(1, 8), 7)
print 'data: ', data
heapq.heapify(data)
show_tree(data)

heap = []
while data:
  i = heapq.heappop(data)
  print 'pop %3d:' % i
  show_tree(data)
  heap.append(i)
print 'heap: ', heap

Imprimer les résultats

data: [4, 1, 3, 7, 5, 6, 2]

         1
    4         2
  7    5    6    3
------------------------------------

pop  1:
         2
    4         3
  7    5    6
------------------------------------
pop  2:
         3
    4         6
  7    5
------------------------------------
pop  3:
         4
    5         6
  7
------------------------------------
pop  4:
         5
    7         6
------------------------------------
pop  5:
         6
    7
------------------------------------
pop  6:
        7
------------------------------------
pop  7:

------------------------------------
heap: [1, 2, 3, 4, 5, 6, 7]

Vous pouvez voir qu'il a tas séquentiel mis en file d'attente.

heapq.heapreplace(iterable, n)

Supprime l'élément existant et le remplace par une nouvelle valeur.

data = random.sample(range(1, 8), 7)
print 'data: ', data
heapq.heapify(data)
show_tree(data)

for n in [8, 9, 10]:
  smallest = heapq.heapreplace(data, n)
  print 'replace %2d with %2d:' % (smallest, n)
  show_tree(data)

Imprimer les résultats

data: [7, 5, 4, 2, 6, 3, 1]

         1
    2         3
  5    6    7    4
------------------------------------

replace 1 with 8:

         2
    5         3
  8    6    7    4
------------------------------------

replace 2 with 9:

         3
    5         4
  8    6    7    9
------------------------------------

replace 3 with 10:

         4
    5         7
  8    6    10    9
------------------------------------

heapq.nlargest (n, itérable) et heapq.nsmallest(n, iterable)

renvoie les n valeurs maximales et minimales de la liste

data = range(1,6)
l = heapq.nlargest(3, data)
print l     # [5, 4, 3]

s = heapq.nsmallest(3, data)
print s     # [1, 2, 3]

PS : Un problème de calcul
Construction d'un exemple de code de tas minimum avec le nombre d'éléments K=5 :

#!/usr/bin/env python 
# -*- encoding: utf-8 -*- 
# Author: kentzhan 
# 
 
import heapq 
import random 
 
heap = [] 
heapq.heapify(heap) 
for i in range(15): 
 item = random.randint(10, 100) 
 print "comeing ", item, 
 if len(heap) >= 5: 
  top_item = heap[0] # smallest in heap 
  if top_item < item: # min heap 
   top_item = heapq.heappop(heap) 
   print "pop", top_item, 
   heapq.heappush(heap, item) 
   print "push", item, 
 else: 
  heapq.heappush(heap, item) 
  print "push", item, 
 pass 
 print heap 
pass 
print heap 
 
print "sort" 
heap.sort() 
 
print heap

Résultat :

Pour plus d'articles liés à l'utilisation du module heapq en Python, veuillez faire attention au site Web PHP chinois !