我记得堆可用于搜索元素是否在其中，时间复杂度为 O(logN)。但突然我无法得到细节。我只能找到getmin delete add等。
有人可以给个提示吗？
问问题
76335 次
8 回答
65
您需要搜索堆中的每个元素以确定元素是否在其中。
不过，一种优化是可能的（我们在这里假设一个最大堆）。如果您到达的节点的值低于您正在搜索的元素，则无需从该节点进一步搜索。但是，即使进行了这种优化，搜索仍然是 O(N)（需要平均检查 N/2 个节点）。
于 2010-03-03T18:08:11.240 回答
3
为时已晚，但仍然为可能会在这里绊倒的人添加此内容。
实际上，在堆中搜索将需要 O(N) 时间。但是，如果您可以在一次预处理中按顺序弹出数组中的所有元素，您将得到一个 O(N.logN) 的排序数组。实际上是堆排序。现在可以在 O(logN) 时间内搜索到您的新排序数组。
于 2019-07-29T15:18:43.850 回答
3
为堆的值添加索引可以解决这个问题。在 python 中，它可以在字典的帮助下完成。每次在最小堆中执行操作时，更新字典中节点的索引。
如果您的最小堆的长度很大并且您想多次在最小堆中搜索，您应该只执行此操作。它需要一些额外的代码来跟踪索引，但这将使程序的速度至少提高 50 - 60%。
于 2019-10-02T14:57:05.647 回答
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关联的项目更改为项目。这将需要“reheapify”以确保维持堆顺序。
实现有点棘手，因为您需要确保堆和索引数组始终同步并指向正确的对象。如果您已经知道如何实现常规堆，请尝试添加索引数组并查看需要更改哪些内容以保持正确的顺序。这是一个完整的实现https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html
于 2020-09-04T17:15:20.407 回答
1
我认为您正在寻找的是 BST（二叉搜索树）。
于 2010-03-03T16:29:19.170 回答
1
在最坏的情况下，在堆中查找元素的时间复杂度仍然是 O(n)。如果你必须找到一个特定的元素，你应该使用二叉搜索树来计算 O(logn) 时间复杂度
堆更擅长查找/查找最大值 (O(1))，而 BST 擅长所有查找 (O(logN))。
于 2021-09-07T21:33:12.500 回答
0
在堆中，最高（或最低）优先级元素始终存储在根。但是，堆不是排序结构。可以认为是部分有序的。
于 2021-12-14T20:06:35.307 回答
0
我对它有点困惑，只是为了说清楚，对于堆（尚未排序），如果你想搜索一个项目，那么它O(n)就像一个未排序的数组一样，但如果它是堆排序的，那么它意味着数组已经排序，所以在这种情况下，将需要O(log n)（二分搜索）来搜索一个项目。
于 2021-05-10T10:04:18.063 回答