python-3.x 如何在Heapq中查找元素的位置

xvw2m8pv  于 2023-06-25  发布在  Python
关注(0)|答案(2)|浏览(188)

我试图使用Python实现HeapQ,但我坚持在这个场景中,我需要获得密钥在队列中的位置?.我想解决这个问题时遇到了困难。任何提示将不胜感激。

bvjxkvbb

bvjxkvbb1#

Python内置heapq实现了一个min堆。所以,如果你的key是minimum,那么key的index是零。如果你想找到任何其他元素的索引,只需要在列表中使用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))
yhxst69z

yhxst69z2#

默认情况下,二进制堆不提供查找堆中元素位置的简单方法。如果你需要这样做,最常见的(可能也是最有效的?)策略是在二进制堆旁边维护一个辅助表,将每个项Map到堆中的索引。然后,每当二进制堆交换两个元素时,它就会更新表,以反映这些元素的位置已经改变。
不幸的是,没有一种简单的方法将此功能添加到库中给定的现有优先级队列实现中。为了做到这一点,您可能必须从头实现自己的二进制堆。

相关问题