Peeking dans un tas en python
Question
Quelle est la façon officielle de jeter un oeil dans un tas de python comme créé par les libs heapq? En ce moment j'ai
def heappeak(heap):
smallest = heappop(heap)
heappush(heap, smallest)
return smallest
qui est sans doute, pas très agréable. Puis-je suppose toujours que heap[0]
est le sommet du tas et l'utiliser? Ou serait-ce prendre trop de la mise en œuvre sous-jacente?
La solution
Oui, vous pouvez faire cette supposition, car il est indiqué dans le :
Heaps sont des tableaux pour lesquels
heap[k] <= heap[2*k+1]
etheap[k] <= heap[2*k+2]
pour tous k , le comptage des éléments de zéro. Pour l'amour de comparaison, les éléments non-existants sont considéré comme infini. propriété intéressante d'un tas est queheap[0]
est toujours le plus petit élément.
(Et c'est probablement la raison pour laquelle il n'y a pas de fonction peek
:. Il n'y a pas besoin pour cela)
Autres conseils
Si vous utilisez Python 2.4 ou plus récent, vous pouvez également utiliser heapq.nsmallest ().