Find the Second Smallest Value Without Removing Anything
Find the Second Smallest Value Without Removing Anything
Complete heap_peek_second(heap, out). It puts the second smallest value of the heap in *out and returns 1, without removing or moving anything. When the heap holds fewer than two values it returns 0 and leaves *out alone, just like heap_peek does for an empty heap.
Reminder: what a parent promises. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps. Every parent is smaller than or equal to its children, so the smallest value is at index 0, and the two children of the root sit at index 1 and index 2. It is NOT a binary search tree: nothing orders a left child against its right sibling, so either child can be the smaller one.
index: 0 1 2 3 4 5 6
value: 1 6 2 8 7 5 3
1 row 0: the smallest value
/ \
[6] [2] row 1: the only two candidates
/ \ / \
8 7 5 3 row 2: each one sits under 6 or under 2
5 and 3 are smaller than 6, but they sit under 2, so they cannot beat 2.
second smallest = the smaller of index 1 and index 2 = 2Why only index 1 and index 2? Every value below row 1 has a path up to the root, and that path passes through index 1 or index 2. Values never grow on the way up, so the child of the root on that path is smaller than or equal to the deeper value. Once the root is set aside, the smallest of everything left is one of its two children, so you compare two slots instead of searching the whole array.
Requirements:
1. When heap->size is less than 2, return 0 and do not touch *out.
2. Otherwise put the smaller of index 1 and index 2 in *out and return 1. When the two are equal, either one gives the same value.
3. With exactly two values, index 2 is outside the heap, so the answer is index 1. Read heap->data[2] only when 2 < heap->size: the slot can still hold an old number that is no longer part of the heap.
4. Equal values count separately: when the root and a child are both 2, the second smallest is 2.
5. Do not change the heap. Leave the struct, heap_init, heap_load, heap_is_empty, heap_peek and heap_print as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 1 8 2 9 10 3 4 smallest: 1 second smallest: 2 MinHeap: 2 3 9 4 5 10 11 smallest: 2 second smallest: 3
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...