Search an element in a heap

Question

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?

Solution 1

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

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).

Solution 2

As mentioned by others, search in a PriorityQueue is linear, as it has no notion of where to look for a particular key other than the root of the heap. This is the main difference from a BST, where you always know to go either left or right depending on the value you are searching. In a heap, the smallest is always at the root, and the child can be on either the left or right subtree.

However, you can modify the PriorityQueue to keep an additional index array which maps an index k to its location in the heap array. This will allow the following operations:

void insert(int k, Item item) : insert item and associate it with k, so that you can later access it directly by by k

Item get(k) : return the item associated with index k. This could be anywhere in the heap.

void change(int k, Item item) : change the item associated with k to item. This will require a "reheapify" to ensure the heap order is maintained.

The implementation is somewhat tricky as you need to ensure the heap and index array are always in sync and pointing to the correct object. If you already know how to implement a regular heap, try adding the index array and see what needs to change to maintain the correct order. Here's a full implementation https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

Solution 3

Too late, but still adding this for someone who might stumble in here.

Search in a heap, as it is, will need O(N) time. But if you can take the hit of one time pre-processing of popping out all the elements sequentially in an array, you'll get a sorted array in O(N.logN). Effectively a heap sort. Now your new sorted array can be searched through in O(logN) time.

Solution 4

Adding an index to the values of heap can solve this problem. In python it can be done with the help of a dictionary. update the index of the node in the dictionary every time you perform an operation in the min heap.

You should only implement this if the length of your min heap is huge and you want to search in the min heap many times. It will require some over head to code for tracking the index but this will increase the speed of the program by at least 50 - 60%.

Solution 5

In the worst case, the time complexity for finding elements in heap is still O(n). You should use a binary search tree for O(logn) time complexity if you have to find a particular element

Heap is better at finding/find max (O(1)), while BST is good at all finds (O(logN)).

View more solutions

Comments

[Saurabh]

Not helpful if you already have a priority queue and want to check whether it contains a given element.

[James Sanders]

Is this entirely true? Take the following Heap as an example: [5, 4, 1, 3 ] If I search this heap (in the form of an array) for the number 3 I will hit 1 and, according to your algorithm, stop here concluding it is not in the heap when it in fact is? Am I missing something here?

[Anonym Mus]

With the optimization, the subtree with root 1 will not be searched further, as it cannot contain 3. 3 is in another subtree. I agree that a linear search (as opposed to a recursive one) can give a wrong answer.

[lee]

@JamesSanders It is true in all cases, even for a linear search. The complete binary tree will have the value 3 as a left child of 4, and 1 will be at same height as 4. Even if you are doing a linear search, the optimization says that 4 > 3, thus you must, at a minimum, compare the children of 4, in addition to all other elements at the same height as 4.

[Xwtek]

@finnw you can make the item in heap and BST reference each other.

[Prof.Chaos]

Can you please elaborate on this response? Search in a heap should always take O(n), and there is no such thing as a sorted heap. I believe what you mean is a sorted array -- which you might of course also do with heap, i.e., via heap search. So your log(n) response is just very odd as it has, I believe, nothing to do with heaps at all. You essentially just say that searching in a sorted array takes O(log(n)), which is just massively missing the point.

[etang]

@AnonymMus How to derive N/2 average search time?