搜索堆中的元素

我记得可以使用堆来搜索元素是否在O（logN）时间复杂度中。但突然间我无法了解细节。我只能找到getmin删除添加等。搜索堆中的元素

任何人都可以提示吗？

2010-03-03 skydoor

您需要搜索堆中的每个元素以确定元素是否在里面。

尽管（我们假设这里有一个最大堆），但是可以进行一次优化。如果您到达的节点值低于要搜索的元素的值，则不需要从该节点进一步搜索。但是，即使使用此优化，搜索仍然是O（N）（需要平均检查N/2个节点）。

2010-03-03 18:08:11

这完全是真的吗？以下面的堆为例： '[5,4,1,3]'如果我为数字3搜索这个堆（以数组的形式），我将按1并根据您的算法在此停止当它实际上不是它堆在一堆时？我在这里错过了什么吗？ –

通过优化，具有根1的子树不会被进一步搜索，因为它不能包含3. 3在另一个子树中。我同意线性搜索（而不是递归）可以给出错误的答案。 –

@JamesSanders在所有情况下都是如此，即使是线性搜索。完整的二叉树的值为3，左边的孩子为4，1与4的高度相同。即使您正在进行线性搜索，优化也表示4> 3，因此您必须至少，比较4的孩子，除了与4高度相同的所有其他元素。 – lee

我认为你要找的是一个BST（二叉搜索树）。

2010-03-03 16:29:19 zarkon

+13

如果您已经拥有优先级队列并且想检查它是否包含给定元素，那么这将毫无帮助。 – finnw

回答