Я обнаружил интересную ошибку в программе, которую реализовал несколько лениво, и подумал, правильно ли я ее понимаю.Короткая версия состоит в том, что Реализация heapq в Python на самом деле не упорядочивает список, а просто обрабатывает список кучи.В частности, я ожидал, что heapify() приведет к упорядоченному списку, который упростит понимание списка упорядоченным образом.
Использование примера приоритетного вызова, как в документации Python:
from heapq import heapify, heappush, heappop
from random import shuffle
class Item(object):
def __init__(self, name):
self.name = name
lst = []
# iterate over a pseudo-random list of unique numbers
for i in sample(range(100), 15):
it = Item("Some name for %i" % i)
heappush(lst, (i, it))
print([i[0] for i in lst])
В результате мы получим
>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]
. Это, как мы отмечаем, не оригинальное упорядочение списка , а, по-видимому, некоторое упорядочение по центру кучи, как описано здесь .Я лениво ожидал, что это будет полностью упорядочено.
В качестве теста, запуск списка через heapify () не даст никаких изменений (так как список уже упорядочен в куче):
heapify(lst)
print([i[0] for i in lst])
>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]
В то время как итерация по списку с помощью функции heappop() приводит к упорядочению, как и ожидалось:
lst2 = []
while lst: lst2.append(heappop(lst))
print([i[0] for i in lst2])
>>> [2, 7, 10, 22, 27, 32, 33, 40, 45, 51, 67, 69, 89, 94, 97]
Итак, heapq не упорядочивает список (по крайней мере, в человеческом смыслеслово), но скорее функции heappush() и heappop() способны вывести упорядоченный список в кучу.
Результат: любые операции срезов и обработки списка в heapified списке приведут кнеупорядоченные результаты.
Это правда, и это всегда верно?
(КСТАТИ: Python 3.0.1 в системе WinXP)