CJCoding With Joseph
15free / daySign inCreate account

Sort an Array With a Temporary Heap

Complete min_heap_sort. It sorts a plain array of ints into ascending order by pushing the values through a min heap. The heap functions it needs are already written.

Reminder: how this min heap is stored. A min_heap is a struct with three fields: capacity (the most values it can hold), count (how many it holds now) and values (a pointer to an array made with malloc). The heap is a complete binary tree kept in that array, filled row by row with no gaps, so only slots 0 to count - 1 are in use. Every parent is smaller than or equal to its children, so the smallest value is always at index 0. For the value at index i, the parent is at (i - 1) / 2 and the children are at 2 * i + 1 and 2 * i + 2.

A min heap always gives you its smallest value first. So if you put every value in a heap and then remove them one at a time, they come out in sorted order. The heap is only a tool here: the function makes it, uses it, and must destroy it before returning, or its memory leaks.

values:  7  2  9  4                      (the caller's array)

step 1: make a heap with room for 4, and heapify the values into it

             2
            / \
           4   9
          /
         7

step 2: remove four times, writing each value back into the array

   remove -> 2   goes to values[0]
   remove -> 4   goes to values[1]
   remove -> 7   goes to values[2]
   remove -> 9   goes to values[3]

step 3: destroy the heap

min_heap_remove writes the removed value through a pointer. The address of slot i of the array is &values[i], so the value can be written straight into the array.

Requirements: 1. Make a heap with room for count values using min_heap_initialize. 2. Put all the values in it with min_heap_heapify. 3. Remove count times, writing the removed values into values[0], values[1], and so on. 4. Destroy the heap with min_heap_destroy before returning.

Do NOT write a main function.

Expected Output:

before: 7 2 9 4 2 8 1 5
after:  1 2 2 4 5 7 8 9

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