CJCoding With Joseph
15free / daySign inCreate account

Remove the Root of a Heap With Three Children per Node

A heap does not have to be a binary tree. In a TERNARY heap every node has up to three children, which makes the tree shorter. Write ternary_remove: it removes the smallest value from a ternary min heap, hands it back through the pointer value, and returns true, or returns false when the heap is empty.

Reminder: the same struct, different index math. The heap is still a min_heap struct (capacity, count, and a values array from malloc), still filled row by row with no gaps, and every parent is still smaller than or equal to its children, so the smallest value is at index 0. Only the arithmetic changes. In a ternary heap the children of index i are at 3 * i + 1, 3 * i + 2 and 3 * i + 3, and the parent of index i is at (i - 1) / 3.

index:   0 | 1  2  3 | 4  5  6
values:  1 | 5  3  4 | 9  6  8

               1                   children of index 0: indexes 1, 2, 3
          /    |    \              children of index 1: indexes 4, 5, 6
         5     3     4
       / | \
      9  6  8

remove: the last value (8) goes to the root, then sinks.
its children are 5, 3 and 4. the SMALLEST of the three is 3, and 8 > 3, so they swap:

               3
          /    |    \
         5     8     4          8 is now at index 2, whose children would start
       / |                      at index 7: there are none, so it stops
      9  6

The shape of the function is the same as the lab's remove. The new part is choosing among up to three children, and a node may have three, two, one or none of them. A child exists only when its index is less than count.

Requirements: 1. When the heap is empty, return false and leave *value alone. 2. Copy the root into *value, subtract 1 from count, and move the value from the old last slot into index 0. 3. Starting at index 0: while there is a first child at 3 * i + 1, find the smallest of the children that exist (on a tie, the one with the lowest index); stop when the value is less than or equal to it, otherwise swap them with swap_values and continue from that child. 4. Return true.

Do NOT write a main function.

Expected Output:

removed 1
[3, 5, 8, 4, 9, 6]
removed 3
[4, 5, 8, 6, 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.