是否真的有可能在常数时间内获得具有特定优先级的堆数组中的对象的位置?
例如,你有一个最大堆 H = [15, 14, 13, 10, 5, 2, 3, 0],你应该给出数组 H 中优先级为 10 的对象的位置,即4.
我不知道如何在不搜索数组的情况下解决这个问题,但是搜索算法不能在常数时间内执行。
有什么想法或提示吗?
提前致谢
问候
最佳答案
简而言之,唯一的方法是在计数时删除项目,然后将它们全部添加回去。或者还有其他具有相同渐近运行时间的选项。
堆属性只保证最小(或最大)元素是根。它没有说明其他项目的订购方式。
如果您将问题更改为二叉搜索树,则答案会有所不同(尽管仍然不是恒定时间)。
此外,如果您将问题从“优先级”更改为“树位置”,答案也会不同。
关于algorithm - 如何在恒定时间内获得具有特定优先级的堆数组中元素的位置?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24376036/