Как эффективно вытолкнуть все элементы с наименьшим ключом в 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

Я собирался предложить изменение структуры с кучи (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()

Answer 2

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

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, если куча пуста.