如何在固定时间内获取具有特定优先级的Heap-Array中元素的位置？

Question

真的有可能在固定时间内以特定优先级获取对象在Heap-Array中的位置吗？

例如，你有一个max-heap H= 15，14，13，10，5，2，3，0，你应该给出数组H中优先级为10的对象的位置，即4。

我不知道如何在不搜索数组的情况下解决这个问题，但是搜索算法不能在固定的时间内执行。

有什么想法或建议吗？

提前感谢

问候

Answer 1

简而言之，要做到这一点，唯一的方法是在计数时删除项目，然后将它们全部添加回来。或者，还有其他选项具有相同的渐近运行时。

heap属性只保证min (或max)元素是根元素。它没有说明其他项目是如何排序的。

如果你把你的问题改成二叉树，答案就不一样了(尽管仍然不是恒定的时间)。

此外，如果将问题从“优先级”更改为“树位置”，答案也会有所不同。