搜索的元素在堆 [英] Search an element in a heap

问题描述

我记得堆可以用于搜索的元素是否在与否与O（logN）的时间复杂度。但是突然我不能让细节。我只能找到getmin删除添加等等。

I remembered that heap can be used to search whether an element is in it or not with O(logN) time complexity. But suddenly I can't get the details. I can only find getmin delete add and so on.

任何人都可以给一个提示？

Can anybody give a hint?

推荐答案

您需要通过每一个元素来搜索堆，以确定是否一个元素在里面。

You need to search through every element in the heap in order to determine if an element is inside.

一个优化是可能的，但（我们假定最大堆在这里）。如果你已经达到一个较低的值比您正在搜索的元素节点，您不需要从该节点进一步搜索。然而，即使有这样的优化，搜索仍然是O（N）（需要检查的平均N / 2个节点）。

One optimization is possible, though (we assume a max heap here). If you have reached a node with a lower value than the element you are searching for, you don't need to search further from that node. However, even with this optimization, search is still O(N) (need to check N/2 nodes in average).

这篇关于搜索的元素在堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！