CJCoding With Joseph
15free / daySign inCreate account

Free a Heap Without Leaking Memory

Complete min_heap_destroy. It gives back all the memory a heap uses.

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 heap is two blocks of memory: the struct, and the array its values pointer points to. Both came from an allocation, so both must be freed, and the ORDER matters. The only place that remembers where the array lives is the values field inside the struct. Free the struct first and that address is gone, so the array can never be freed (a memory leak), and reading a field of a freed struct is a bug.

  the struct                  the array
  +--------------+            +----+----+----+
  | capacity: 3  |            |  4 |  9 |  6 |
  | count:    3  |            +----+----+----+
  | values:  ----+----------->
  +--------------+

  step 1: free the array      (follow the arrow while it still exists)
  step 2: free the struct

So that the tests can SEE whether memory was returned, this file uses tracked_malloc and tracked_free. They work exactly like malloc and free, and they also keep a count of the blocks that are still in use.

Requirements: 1. Free the array of values with tracked_free. 2. Then free the heap struct itself with tracked_free. 3. Free the array first.

Do NOT write a main function.

Expected Output:

blocks in use before: 2
blocks in use after: 0
freed first: the array

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

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