CJCoding With Joseph
15free / daySign inCreate account

Delete the Value at Any Index

Complete heap_delete_at(MinHeap *heap, int i, int *removed). It deletes the value at any index i, not only the root: it puts that value in *removed, keeps the heap valid, and returns 1. For an index outside the heap it returns 0 and changes nothing.

Reminder: filling a hole in a min heap. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps, so a deleted slot has to be filled, and the only value you can move without opening a new gap is the LAST one. Every parent is smaller than or equal to its children, and the parent of index i is (i - 1) / 2. Remove does this at the root, where the moved value can only go down. In the middle of the tree the last value may come from a different branch, so it can be too big for its new slot or too small for it. When it came from under slot i, like 4 in the second example below, it is never smaller than its new parent, so it can only sink or stay.

the heap before either delete (4 is the last value):

index:   0   1   2   3   4   5   6
value:   1  10   2  11  12   3   4

            1
          /   \
        10     2
        / \   / \
      11  12 3   4

delete index 3 (the value 11): the last value 4 fills the hole

            1
          /   \
        10     2
        / \   /
       4  12 3           4 < its parent 10: send it UP

            1
          /   \
         4     2         after heapify_up: 4 went up, 10 came down
        / \   /
      10  12 3

index:   0   1   2   3   4   5
value:   1   4   2  10  12   3

delete index 2 (the value 2) from the first heap instead: 4 fills that hole

            1
          /   \
        10     4         4 > its parent 1: send it DOWN
        / \   /
      11  12 3

            1
          /   \
        10     3         after heapify_down: 4 went down, 3 came up
        / \   /
      11  12 4

index:   0   1   2   3   4   5
value:   1  10   3  11  12   4

So once the last value fills slot i, ask its new parent which way to go. Smaller than the parent means it climbs with heapify_up. Otherwise it may be too big for its new children, so heapify_down gets the chance to sink it, and when it already fits, heapify down simply stops at once. If i was the last slot, nothing has to move: shrinking the heap is the whole job.

Requirements: 1. Return 0 when i is less than 0 or not smaller than heap->size, and change nothing, *removed included. An empty heap has no valid index. 2. Otherwise put the value at index i in *removed and shrink the heap by one. 3. If i was the last slot (after the shrink, that means i equals heap->size), you are done. Otherwise copy the last value into slot i, then call heapify_up(heap, i) when it is smaller than its parent (index 0 has no parent), or heapify_down(heap, i) otherwise. Both are provided. 4. Return 1. 5. Leave the provided helpers as they are.

Do NOT write a main function.

Expected Output:

MinHeap: 1 3 2 7 4 5 6 9 8 12
delete index 1: yes, removed 3
MinHeap: 1 4 2 7 12 5 6 9 8
delete index 2: yes, removed 2
MinHeap: 1 4 5 7 12 8 6 9

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