CJCoding With Joseph
15free / daySign inCreate account

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   3

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

Hints2 available
Topics:
Data Structures & AlgorithmsHeaps
1
Tab to indent (Esc then Tab to move on) · Ctrl+Enter to run · Shift+Alt+F to format · Ctrl+Space to expand shortcuts (p, fori)

Your Output

Run your code to see the output here...

Test Cases

Run your code to see test case results.