搜索堆中的元素

Question

我记得堆可以用来搜索元素是否在其中,具有O(logN)时间复杂度.但突然间我无法得到细节.我只能找到getmin delete add等等.

任何人都可以暗示一下吗？

Answer 1

您需要搜索堆中的每个元素,以确定元素是否在内部.

但是,一种优化是可能的(我们假设这里有一个最大堆).如果到达的节点的值小于要搜索的元素的值,则无需从该节点进一步搜索.但是,即使进行了这种优化,搜索仍然是O(N)(需要平均检查N/2个节点).

Answer 2

正如其他人所提到的，PriorityQueue 中的搜索是线性的，因为它不知道在哪里查找除堆根之外的特定键。这是与 BST 的主要区别，在 BST 中，您始终知道根据要搜索的值向左或向右移动。在堆中，最小的始终位于根，子树可以位于左子树或右子树上。

但是，您可以修改 PriorityQueue 以保留一个附加索引数组，该数组将索引 k 映射到其在堆数组中的位置。这将允许执行以下操作：

void insert(int k, Item item)：插入item并将其与k关联起来，这样以后就可以直接通过k访问它

Item get(k)：返回与索引 k 关联的项目。这可能位于堆中的任何位置。

void change(int k, Item item)：将与k关联的item更改为item。这将需要“重新堆化”以确保维持堆顺序。

实现有点棘手，因为您需要确保堆和索引数组始终同步并指向正确的对象。如果您已经知道如何实现常规堆，请尝试添加索引数组并查看需要更改哪些内容才能保持正确的顺序。这是完整的实现https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html