Print a Heap One Row at a Time
Print a Heap One Row at a Time
Complete heap_print_rows(heap). It prints the heap the way you would draw it, one tree row per line: Row 0: with the root, Row 1: with its two children, and so on down to the last row.
Reminder: array order is row order. A min heap is a complete binary tree kept in an array, filled row by row, left to right, with no gaps. That means the array already lists the rows one after another, so you only have to know where each row starts and where it ends. Every row except the last one is full, and the last row fills from the left.
5 row 0 = index 0
/ \
7 6 row 1 = index 1 to 2
/ \ / \
9 8 10 11 row 2 = index 3 to 6
/ \ /
15 12 13 row 3 = index 7 to 14 (only 7 to 9 used)
index: 0 | 1 2 | 3 4 5 6 | 7 8 9
value: 5 | 7 6 | 9 8 10 11 | 15 12 13Row 0 holds 1 slot, row 1 holds 2, row 2 holds 4 and row 3 holds 8: each row is twice as wide as the one above it, and it starts right after the last slot of the row before. In numbers, row r runs from index 2^r - 1 to index 2^(r+1) - 2, where 2^r means 1 doubled r times, so 2^0 is 1, 2^1 is 2, 2^2 is 4 and 2^3 is 8. In C, ^ is a different operator, so keep a running width and double it instead. Only the last row can be short, so stop at heap->size even in the middle of a row. For the heap above the function prints four lines, and the last one, Row 3: 15 12 13, holds only three values.
Requirements:
1. When the heap is empty, print (empty) and a newline, and nothing else.
2. Otherwise print one line per row from row 0 down: Row r: and then the values of that row in array order, each with one space before it, for example Row 1: 7 6. No space at the end of a line.
3. Row r starts at index 2^r - 1 and holds 2^r slots. The last row stops at heap->size even when it is not full, and a row with no values in it is never printed.
4. Do not change the heap. Leave the struct, heap_init, heap_load and heap_print as they are.
Do NOT write a main function.
Expected Output:
MinHeap: 1 3 2 7 4 5 Row 0: 1 Row 1: 3 2 Row 2: 7 4 5 MinHeap: 2 4 3 8 5 6 9 12 10 7 11 13 Row 0: 2 Row 1: 4 3 Row 2: 8 5 6 9 Row 3: 12 10 7 11 13
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...