查找堆中元素的位置

考虑以下元素列表。

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，这样，如果我们跟踪从堆中弹出项目的次数，我们就知道它的位置。然而，当我们修改堆本身时，这不是很有效。

有更好的方法来解决问题吗？

从注释中的澄清来看，您似乎想将堆视为完全排序的数据结构，并查找小于或大于特定元素的元素数量。

堆并不是为支持此操作而设计的。如果你想做这种事情，你应该使用这样的数据结构：is专为它而设计。例如，sortedcontainers.SortedList http://www.grantjenks.com/docs/sortedcontainers/sortedlist.html:

import sortedcontainers

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

index = l.index(39)

如果你真的想使用堆，你可以运行贪心搜索 https://stackoverflow.com/questions/31495693/creating-a-sorted-array-from-the-smallest-log-n-tems-in-a-heap堆中，并在找到要查找的项目时停止。对于低优先级的项目来说，这将是非常昂贵的；在最坏的情况下，它将具有完整排序的时间复杂度，并且常数因子更差。