在堆中查找元素的位置

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为止，并且记录我们从堆中弹出元素的次数，这样我们就可以知道它的位置。然而，这并不是很高效，因为我们会修改堆本身。

有没有更好的解决方法呢？

- Jonathan

---

“Position” 指的是什么？是大于它的元素数量吗？还是表示堆的物理列表中的索引？或者其他什么？你为什么要这样做呢？你需要一个 decrease-key 操作吗？还是你试图将堆视为完全排序的数据结构？ - user2357112

@user2357112 我想知道大于给定数字的元素数量。在39的情况下，有6个大于39的元素，因此39将位于第7个位置或排名。我想知道的原因是，如果您正在使用堆来实现优先队列，则知道元素所在的位置将非常有用。 - Jonathan

Sedgewick的书《算法》描述了一种间接堆，它使用初始数组的索引（而不是重新排序）并允许通过索引进行“更改键”操作（用于Dijkstra算法）。有关参考-在此Java代码中的class PQi：http://www.cs.princeton.edu/~rs/Algs3.java1-4/code.txt - MBo

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)

如果您仍然想使用堆，可以对堆进行贪婪搜索，并在找到所需项时停止。这将非常耗费低优先级项的时间；最坏情况下，它将具有完整排序的时间复杂度，并且恶化因子更差。

- user2357112

---

感谢您澄清堆不支持该操作。 - Jonathan

Answer 2

如果你想保留堆，也许可以尝试这样做：

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

print(ordered.index(39))

如果不是这种情况，也许使用排序会更适合你：

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

文档说：

这两个函数使得将堆视为普通的Python列表成为可能，而不会有任何意外：heap[0]是最小的元素，heap.sort()维护了堆的不变性！

- BPL

---

是的，那确实解决了问题，但从大O复杂度的角度来看，这不是一个很好的解决方法。我在想是否有更好的解决问题的方法。 - Jonathan

Answer 3

根据你提供的数据，我认为这只是简单的算术问题。你需要倒数第39个索引，对吗？

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

这将导致从堆的“右”端开始，基于0的计数的正确索引。

- Prune