Как найти положение элемента в Heapq

Question

Я пытаюсь реализовать HeapQ с использованием Python, но я застрял в этом сценарии, где мне нужно получить положение ключа в очереди?, Я ударил стену, пытаясь решить эту проблему. Любые советы будут оценены.

Answer 1

Двоичные кучи по умолчанию не предоставляют простого способа найти положение элемента в куче. Если вам нужно это сделать, наиболее распространенной (и, вероятно, наиболее эффективной?) стратегией является поддержка вспомогательной таблицы рядом с двоичной кучей, сопоставляющей каждый элемент с его индексом в куче. Затем, всякий раз, когда двоичная куча меняет местами два элемента, она обновляет таблицу, чтобы отразить, что позиции этих элементов изменились.

К сожалению, не существует простого способа добавить эту функциональность к существующей реализации очереди приоритетов, представленной в библиотеке. Для этого вам, возможно, придется создать собственную двоичную кучу с нуля.

Answer 2

Встроенная куча Python реализует минимальную кучу. Итак, если ваш ключ минимален, то индекс ключа равен нулю. Если вы хотите найти индекс любого другого элемента, просто используйте метод index в списке. См., например, приведенный ниже код.

      import heapq
numbers = [1, 11, 2, 5, 3, 9, 6]

heap = [] # a list which will be used as heap

for number in numbers:
    heapq.heappush(heap, number)

# heapq is min heap. The minimum element will be at the root or index 0.
# The following line will print 1 as it is the minimum in the list.
print(heap[0]) 

# To find a element index just use the index function on the list
print(heap.index(11))