40

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?

1
  • element in it or not... is more a hash table application.
    – Sandeep T
    Commented Jan 5 at 4:50

8 Answers 8

77

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

6
  • 7
    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?
    – sanjams
    Commented Sep 22, 2016 at 12:54
  • 3
    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.
    – rettvest
    Commented Sep 22, 2016 at 22:08
  • 3
    @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.
    – lee
    Commented Nov 24, 2016 at 13:10
  • 2
    @AnonymMus How to derive N/2 average search time?
    – etang
    Commented Sep 25, 2021 at 16:43
  • @lee consider this min-heap [1, 2, 5, 3]. If you search for 3, you cannot stop at 5. Commented Nov 24, 2023 at 3:21
7

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

4

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

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.

1
  • searching all elements O(n) < heapsort O(nlgn) + binaryserach(lgn)
    – Sandeep T
    Commented Jan 5 at 4:46
3

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

1

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

2
  • 26
    Not helpful if you already have a priority queue and want to check whether it contains a given element.
    – finnw
    Commented Jul 16, 2010 at 10:45
  • @finnw you can make the item in heap and BST reference each other.
    – Xwtek
    Commented Oct 6, 2019 at 15:06
0

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.

-1

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.

1
  • 1
    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.
    – Prof.Chaos
    Commented Sep 4, 2021 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.