Как эффективно вытолкнуть все элементы с наименьшим ключом в heapq?

Question

Я работаю над экспериментом по моделированию и пытаюсь сделать свой код максимально эффективным. В одной части у меня есть очередь с минимальной кучей приоритетов, которую я реализовал, используя heapq модуль.

Во время симуляции я должен высовывать все элементы с наименьшим ключом. Простой подход для этого будет:

    elements = []
    k1, v1 = heapq.heappop(heap)
    elements.append((k1,v1))
    k2, v2 = heap[0] #looks at the smallest item without popping
    while(k1 == k2):
         k1, v1 = heapq.heappop(heap)
         elements.append((k1,v1))
         k2, v2 = heap[0]
    return elements

Answer 1

Общая техника, которую вы показываете, является самой эффективной и простой. Но вы делаете дополнительные задания, которые на самом деле не нужны. Ниже приведена небольшая оптимизация.

elements = []
k1, v1 = heapq.heappop(heap)
elements.append((k1,v1))
while(k1 == heap[0]):
     k2, v2 = heapq.heappop(heap)
     elements.append((k2,v2))
return elements

Чтобы быть в безопасности, вы, вероятно, должны добавить проверки, чтобы убедиться, что ваша куча не пуста. проверка heap[0] когда нет элементов в куче, это будет плохо, как если бы heapq.heappop если куча пуста

Answer 2

Я собирался предложить изменение структуры из кучи (k, v) до кучи k и словарь {k:[v]}, Это превратит ваш код в:

k = heap[0]
return [(k,v) for v in hash[k]]

С:

hash = defaultdict(list)
heap = []

heappush(heap, (k, v)) станет:

heappush(heap, k)
hash[k].append(v)

heappop(heap) станет:

k = heappop(heap)
v = hash[k].pop()