CJCoding With Joseph
15free / daySign inCreate account

Sort an Array With a Min Heap

Complete heap_sort(int values[], int count). It sorts the first count values of the array into ascending order with a min heap: build a heap from them, then take the smallest value out count times, writing each one back into the array.

Reminder: what a min heap hands back. 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, so the smallest value is at index 0. build_heap copies any values into a heap and rearranges them. heap_remove takes the root, moves the last value to the root and sinks it down, so the next smallest value is at the root again. Remove over and over and the values come out smallest first.

values:  5  2  8  1  4        count = 5

build_heap copies them into a heap and rearranges the copy:

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

            1
          /   \
         2     8
        / \
       5   4

then heap_remove five times, each removed value going into the next slot of values:

round   removed   heap left     values so far
  1        1      2 4 8 5       1
  2        2      4 5 8         1 2
  3        4      5 8           1 2 4
  4        5      8             1 2 4 5
  5        8      (empty)       1 2 4 5 8

The heap works on its own copy in heap.data, so writing into values while you remove cannot disturb it. Each removal hands back the smallest value still in the heap, so removal number k (counting from 0) belongs in values[k].

Requirements: 1. Declare a MinHeap inside heap_sort and fill it from values with the provided build_heap. 2. Call the provided heap_remove exactly count times. Removal number k, counting from 0, goes into values[k]. 3. When it returns, values[0] to values[count - 1] are in ascending order, repeats included. Slots from values[count] on are not touched. 4. count is between 0 and HEAP_CAPACITY (15). With 0 or 1 values there is nothing to reorder. 5. heap_sort prints nothing. The tests print the array before and after, and one test also calls build_heap on its own heap so you can see the heap it makes. 6. Leave the provided heap functions as they are.

Do NOT write a main function.

Expected Output:

before: 7 -2 9 3 1 8 3 6 0 4
build_heap turns them into
MinHeap: -2 0 3 3 1 8 9 6 7 4
after: -2 0 1 3 3 4 6 7 8 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.