CJCoding With Joseph
15free / daySign inCreate account

Change a Value Inside the Heap

Complete heap_change_value(heap, i, new_value). It overwrites the value at index i with new_value, moves it until the heap rule holds again, and returns 1. When i is not an index inside the heap it returns 0 and changes nothing.

Reminder: a change can only break the rule in one direction. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps, and every parent is smaller than or equal to its children. Insert fixes a new value by bubbling it up (heapify up), and remove fixes the root by sinking it down (heapify down), swapping with the SMALLER child. Both heapify_up and heapify_down are already written for you, and both work from any index, not just the last slot or the root.

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

change index 6 (the 8) to 0: 0 is smaller than 8, so it may need to go UP

  after writing 0           after heapify_up
        1                          [0]
      /   \                       /   \
    4       2       ->          4       1
   / \     / \                 / \     / \
  7   5   3  [0]              7   5   3   2

0 < 2: swap. 0 < 1: swap. 0 is at the root: stop.

index:   0   1   2   3   4   5   6
value:   0   4   1   7   5   3   2

change index 1 to 9 (starting from the first heap again): 9 is bigger than 4, so it may need to go DOWN

  after writing 9           after heapify_down
        1                           1
      /   \                       /   \
   [9]      2       ->          5       2
   / \     / \                 / \     / \
  7   5   3   8               7  [9]  3   8

9 has children 7 and 5. The smaller one is 5, and 5 < 9: swap. 9 is now a leaf at index 4: stop.

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

A value that got smaller can only clash with its parent: its children were already at least as big as the old value, so they are bigger than the new one too. A value that got bigger can only clash with its children: its parent was already no bigger than the old value. So compare the new value with the old one: smaller means heapify_up(heap, i), bigger means heapify_down(heap, i), and the same value means there is nothing to fix.

Requirements: 1. Return 0 and change nothing when i is less than 0 or not less than heap->size. 2. Otherwise remember the old value at index i, store new_value there, then fix the heap: heapify_up(heap, i) when the new value is smaller than the old one, heapify_down(heap, i) when it is bigger, nothing when they are equal. 3. Return 1 for every index inside the heap, even when new_value is the same as the old value or the value does not need to move. 4. Leave the struct and every provided helper (heapify_up, heapify_down and the ones they use) as they are.

Do NOT write a main function.

Expected Output:

MinHeap: 2 5 3 8 6 4 9 10 12
change index 8 to 1: yes
MinHeap: 1 2 3 5 6 4 9 10 8
change index 6 to 7: yes
MinHeap: 1 2 3 5 6 4 7 10 8

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