algorithm - 在最大堆中查找元素

Question

我有一个使用数组存储元素的 MaxPQ 堆。我可以使用什么算法在堆中查找给定元素？我当前使用的算法从索引 1 开始遍历数组，直到添加到堆中的元素数。该算法的复杂度为 O(N)，是否有复杂度为 O(logN) 的算法？

Answer 1

如果您只有一个表示堆（最小值或最大值）的数组，那么恐怕找不到最坏情况的对数算法，因为从树的顶部开始您将无法分辨一般要搜索哪个子树。如果您的根是 100，它的子节点是 90 和 80，而您正在寻找 5，那么您必须（通常）探索这两条路径。

现在，如果您保留一个辅助数据结构来跟踪您的键数组中的位置，您可以进行恒定时间查找。我在http://eclipse.wells.edu/badams/courses/cs322/notes/topics/tools/heap.html找到了以下描述

要查找任意元素，它有助于维护一个附加数组，该数组由节点名称索引并由它们在堆中的位置（指针或索引号）作为键。这使得任意节点的查找在恒定时间内工作，并且维护数组中的数据只需要每个冒泡操作的固定步数，因此不会改变 heapify up 或 down 的渐近时间。

同样，仅考虑堆，您的最坏情况将是线性的，尽管如果您遍历堆并进行一些修剪，您可能会在实践中获得一点加速。