CJCoding With Joseph
15free / daySign inCreate account

Find Where an Array Breaks the Heap Rule

Complete find_heap_violation(values, count). It checks an array of count values against the min heap rule and returns the smallest index whose value is smaller than its parent's value, or -1 when the whole array is a valid min heap.

Reminder: the one rule a min heap keeps. 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. Each line in the tree joins one child to one parent, and the parent of index i is at (i - 1) / 2, so any array can be read as a tree and checked.

index:   0   1   2   3   4   5   6
value:   2   6   3   9   4   5   8

            2
          /   \
         6     3
        / \   / \
       9   4 5   8
           ^
           4 is smaller than its parent 6: the rule breaks at index 4

child    parent    check
  1        0       6 under 2: ok
  2        0       3 under 2: ok
  3        1       9 under 6: ok
  4        1       4 under 6: broken, so the answer is 4
  5, 6     -       never checked: the function already returned 4

Every index except 0 has exactly one parent, so looping over the children, index 1 up to count - 1, and comparing each one with its parent checks every line of the tree exactly once. A check that walks the parents and looks down at their children does the same job from the other side; here you walk the children and look up. Because the loop goes from index 1 upward, the first break it meets is the smallest index, so you can return it straight away.

Requirements: 1. Return the smallest index i, 1 or more, where values[i] is smaller than values[get_parent_index(i)]. 2. Return -1 when there is no such index. An empty array and an array with one value are valid heaps, so both give -1. 3. Equal values are fine: a child equal to its parent does not break the rule. 4. When a parent is too big, the break is reported at its child. In the array 9 4 the answer is 1, the index of the child, never 0. 5. Do not change the array, and leave get_parent_index as it is.

Do NOT write a main function.

Expected Output:

values: 1 4 2 9 5 3 7 12 10 6
result: -1, a valid min heap
values: 1 4 2 9 5 3 7 12 3 6
result: 8, 3 is under its parent 9
values: 1 11 2 9 5 3 7 12 10 6
result: 3, 9 is under its parent 11

= newline. The output ends with a newline — print one after the last line.

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