查找元素在堆中的位置

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)

如果您确实想使用堆，则可以对堆进行贪婪搜索，并在找到要查找的项目时停止。对于低优先级的项目，这将是非常昂贵的；在最坏的情况下，它将具有完整排序的时间复杂度，并且具有更差的常数因子。