CJCoding With Joseph
15free / daySign inCreate account

Swap Two Slots in the Heap Array

Complete swap(MinHeap *heap, int i, int j). It trades the values stored at index i and index j of heap->data, and changes nothing else.

Reminder: swapping is how values move in a heap. A min heap is a complete binary tree kept in an array, and every parent is smaller than or equal to its children. When a value is in the wrong place, the heap fixes it by trading the value with its parent (heapify up, after an insert) or with its smaller child (heapify down, after a remove). Every one of those trades is a call to swap, so this small function does all the moving inside heapify up and heapify down.

BEFORE swap(heap, 5, 2): the 3 at index 5 is smaller than its parent
index:   0   1   2   3   4   5
value:   2   5   4   9   7   3

            2
          /   \
         5     4            <- parent 4, index 2
        / \   /
       9   7 3              <- child 3, index 5

AFTER swap(heap, 5, 2): the two values traded places
index:   0   1   2   3   4   5
value:   2   5   3   9   7   4

            2
          /   \
         5     3            <- 3 moved up to index 2
        / \   /
       9   7 4              <- 4 moved down to index 5

Only two slots of the array change. The catch is that the first assignment overwrites one of the two values, so save that value in a temporary variable before you copy over it, then put the saved value into the other slot. Trade what is stored in the two slots, not the numbers i and j: i and j are only copies of the indexes, so swapping them changes nothing in the heap.

Requirements: 1. After swap(heap, i, j), heap->data[i] holds the old value of heap->data[j], and heap->data[j] holds the old value of heap->data[i]. 2. The order of i and j does not matter, and swap(heap, i, i) leaves the heap exactly as it was. 3. Do not change heap->size or any other slot. The function does not check the heap rule, it only moves the two values. 4. Leave the MinHeap struct, heap_load, get_parent_index and heap_print as they are.

Do NOT write a main function.

Expected Output:

MinHeap: 3 6 5 9 8 1
swap index 5 with its parent, index 2
MinHeap: 3 6 1 9 8 5
swap index 2 with its parent, index 0
MinHeap: 1 6 3 9 8 5

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

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