CJCoding With Joseph
15free / daySign inCreate account

Build a Min Heap From an Unsorted Array

Complete build_heap. It copies count values, in any order, into the heap and then rearranges them into a valid min heap. The sinking is done by the provided heapify_down.

Reminder: fixing a whole array from the bottom up. 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. Copying the values in gives the right shape but the wrong order. A leaf has no children, so it is already a tiny heap on its own, and the last node that does have a child, the last parent, is the parent of the last value at index size - 1. For two or more values that always works out to index size / 2 - 1. Calling heapify_down on every parent, from that one back to the root, fixes the tree from the bottom up: by the time a parent sinks, the subtrees under it are already heaps.

Here the values 8 5 6 2 9 1 are built into a heap:

After the copy: size 6. The last value is at index 5, and its parent
is (5 - 1) / 2 = 2, the same as 6 / 2 - 1. So i runs 2, 1, 0.

            8               index 0: a parent
          /   \
         5     6            index 1 and 2: parents
        / \   /
       2   9 1              index 3, 4, 5: leaves, already heaps

i = 2: 6 has one child, 1. 1 < 6, so swap.

            8
          /   \
         5     1            6 sank to index 5
        / \   /
       2   9 6

i = 1: 5 has children 2 and 9. 2 is smaller and 2 < 5, so swap.

            8
          /   \
         2     1            5 sank to index 3
        / \   /
       5   9 6

i = 0: 8 has children 2 and 1. 1 is smaller and 1 < 8, so swap.

            1
          /   \
         2     8            8 sank to index 2
        / \   /
       5   9 6

       8 keeps sinking: at index 2 its one child is 6, and 6 < 8, so swap again.

            1
          /   \
         2     6
        / \   /
       5   9 8              8 sank to index 5, a leaf: done

index:   0   1   2   3   4   5
before:  8   5   6   2   9   1
after:   1   2   6   5   9   8

Going backwards is what makes it work. heapify_down(i) only sinks the value that starts at index i, and each swap lifts the smaller child just one row, so if you went forwards from the root instead, these values would end as 5 2 1 8 9 6: the 1 gets pulled up only one row and 5 is left sitting at the root.

Requirements: 1. Copy values[0], values[1], ... into heap->data, growing heap->size by one for each value. Stop after HEAP_CAPACITY (15) values even when count is bigger. The starter already sets heap->size to 0. 2. Then call heapify_down(heap, i) for every i from heap->size / 2 - 1 down to 0, in that order. 3. An empty array and a single value need no swaps: heap->size / 2 - 1 is -1 for them, so that loop runs zero times. 4. Duplicates are allowed and are all kept. 5. values is const: read it, never change it. Leave the MinHeap struct and every provided function as they are.

Do NOT write a main function.

Expected Output:

values: 9 4 7 1 8 2 6
MinHeap: 1 4 2 9 8 7 6
valid min heap: yes, size 7
values: 10 9 8 7 6 5 4 3 2 1
MinHeap: 1 2 4 3 6 5 8 10 7 9
valid min heap: yes, size 10

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