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?

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

Answer 2

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.

Answer 3

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

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