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?

Urien

element in it or not... is more a hash table application. – Author

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

Paradigm

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? – Methadone

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. – Paradigm

@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. – Brunn

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

@Brunn consider this min-heap [1, 2, 5, 3]. If you search for 3, you cannot stop at 5. – Mohawk

You always have to check the other side of the tree. Heap only has order relation between parent/child not between siblings. The optimization argued is not an optimization. – Author

Answer 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

Warr

Answer 3

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

Tonguetied

Answer 4

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.

Culbert

searching all elements O(n) < heapsort O(nlgn) + binaryserach(lgn) – Author

Answer 5

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

Elude

Answer 6

I think what you're looking for is a BST (binary search tree).

Ratchford

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

@Elayne you can make the item in heap and BST reference each other. – Dorcasdorcea

Answer 7

In a heap, the highest (or lowest) priority element is always stored at the root. However, a heap is not a sorted structure; it can be regarded as being partially ordered.

Suzansuzann

Answer 8

I was a little bit confused with it, just to make it clear, for heap(not yet sorted) if you want to search an item then it will take O(n) just like an unsorted array, but if it is heap-sorted then it means the array is already sorted so in that case, it will take O(log n) (binary search) to search an item.

Reporter

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. – Manikin