Search a Heap for a Value
Search a Heap for a Value
Complete heap_contains(const MinHeap *heap, int value). It returns 1 when value is stored somewhere in the heap, or 0 when it is not.
Reminder: a min heap is not a binary search tree. A min heap is a complete binary tree kept in an array, and its only rule is that every parent is smaller than or equal to its children. Nothing orders a left child against its right sibling, so a value bigger than the root can sit on either side, at any depth. The shortcut a BST search uses (smaller goes left, bigger goes right) does not work here.
looking for 9
1 a BST search: 9 > 1, so go right
/ \
4 2 9 > 2, so go right again
/ \ / \
9 6 5 3 3 has no children, so "not found"
^
but the 9 was here all along, at index 3
index: 0 1 2 3 4 5 6
value: 1 4 2 9 6 5 3The heap rule tells you where the smallest value is, and that nothing below a node is smaller than it, but it does not tell you which side the value you are searching for is on, or how deep it sits. So the simple search that is always right is to check every slot in use, from index 0 up to size - 1, and stop as soon as one matches.
Requirements:
1. Return 1 as soon as a slot in use holds value. Return 0 only after every slot in use has been checked.
2. Check only the slots in use: a number left over in a slot at size or beyond is not in the heap.
3. An empty heap contains nothing, so return 0 for it. A value stored more than once returns 1, the same as any other match.
4. Searching does not change the heap. Leave heap_init, heap_load and heap_print as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 2 6 3 10 7 5 4 contains 10: yes contains 7: yes contains 2: yes contains 4: yes contains 9: no contains 1: no contains 12: no
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...