查找元素在堆中的位置

Question

请考虑以下元素列表。

h = [38, 203, 1, 45, 39, 10, 34, 90, 10, 2, 100, 1]

如果将其转换为基于数组的堆，它将以以下方式查看。

import heapq

heapq.heapify(h)
# now we have a heap that looks like this
# [1, 2, 1, 10, 39, 10, 34, 90, 45, 203, 100, 38]

找出39在这个堆中的位置的最好方法是什么？

查找的一种方法是从堆中弹出项目，直到它返回39，这样，如果我们跟踪从堆中弹出项目的次数，我们就知道它的位置。但是，当我们修改堆本身时，这并不是很有效。

有没有更好的方法来解决这个问题？

Answer 1

从注释中的说明来看，您似乎希望将堆视为一个完整排序的数据结构，并查找小于或大于特定元素的元素数。

堆不是为支持此操作而设计的。如果您想要这样做，您应该使用为其设计的数据结构。例如，sortedcontainers.SortedList

import sortedcontainers

l = sortedcontainers.SortedList([38, 203, 1, 45, 39, 10, 34, 90, 10, 2, 100, 1])

index = l.index(39)

如果您确实想要使用堆，那么可以运行堆的贪婪搜索，并在单击要查找的项时停止。对于低优先级的项目，这将是非常昂贵的；最坏的情况下，它的时间复杂度将是一个完整的种类，一个更坏的常数因素。

Answer 2

如果您想保留堆，也许这样的东西就可以了：

ordered = []
temp = heap[:]
while temp:
    ordered.append(heapq.heappop(temp))

print(ordered.index(39))

如果不是这样的话，也许使用排序更适合您：

heap.sort()
print(heap.index(39))

文档说：

这两种方法都可以将堆看作一个常规的Python列表，而不会有任何意外:堆是最小的项，而heap.sort()则保持堆不变！

Answer 3

从你给出的数据来看，我认为这是一个简单的算术。你需要倒计时的39指数，对吗？

idx = len(h) - h.index(39) - 1

这将为堆的“右”端的0基计数生成适当的索引。