Theoretically, every data structure is abstract, and is a black box. It's just that the DS provides you with certain functions that let you interact with it. An array provides you with functions to change data. A stack provides you a push and pop. A heap lets you peek minimum, remove minimum, and add a new value
Theoretically, you cannot find the minimum element of a stack without popping from the stack, because you aren't allowed to peep the contents of the stack. But practically, you do it all the time, and it would be inefficient not to.
Similarly, in a practical scenario, a heap is just a collection of memory locations that you handle in a particular way. You can use it in a strict theoretical sense if you wish, but if you need to you can always traverse the nodes.
Coming back to the question,
Pure theoretical way, in which you aren't allowed to traverse the heap:
n = Number of Elements in the Heap
// the variable 'key' holds the value you wish to find in the heap.
temp_list = []
exists_inHeap = False
for index from 1 to n:
element = Heap.removeMin() // get the minimum element from the heap
if element == key:
exists_inHeap = True
break
end if
temp_list[index] = element //Put the element into the temp list,
// because we will need to restore the
// heap at the end.
end for
//Restore the heap
for each element in temp_list:
Heap.insert(element)
end for //Now we know if the element exists in the heap or not.
//If it doesn't exist in the heap already, we insert it.
if not exists_inHeap:
Heap.insert(key)
end if
//Done!
Practical way
// Don't delete and reinsert elements to find
// if our 'key' exists in the heap.
// Simply traverse through the heap and look for
// the 'key' in the heap.
exists_inHeap = False
for each elemenet in Heap:
if element == 'key':
exists_inHeap = True
break
end if
end for
//Now we know if the element exists in the heap or not.
//If it doesn't exist in the heap already, we insert it.
if not exists_inHeap:
Heap.insert(key)
end if
//Done!
