If you just want to know if an element is present or not in a heap, just use hashset in conjunction to the heap. If you want the index of the element also, use a hashmap with the heap elements as keys and their indices as values. You will require an extra auxiliary space of O(1). But it can reduce the time complexity of search to same as hashmap's complexity