Print the Running Median With Two Heaps
Print the Running Median With Two Heaps
Write print_running_medians. It reads an array one value at a time and, after each one, prints the median of all the values read so far. The median is the middle value when they are sorted. With an even number of values there are two middle values: print the LOWER one.
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.
Sorting everything again after each new value would work, but it is slow. Two heaps do it with a few swaps per value. Split the values into a LOW half and a HIGH half. The median is then the LARGEST value of the low half, as long as the low half holds the same number of values as the high half, or one more.
values so far, sorted: 1 2 5 | 8 9
low half: 1 2 5 high half: 8 9
need its LARGEST quickly need its SMALLEST quickly (to pass it over)
a min heap of the NEGATED an ordinary min heap
values: -5 is the root
-5 8
/ \ /
-1 -2 9
median = the low half's largest = -(-5) = 5The heap functions are already written and tested, the same ones as in your lab. As with the lab's header file, this file shows only their prototypes. The lab only has a MIN heap, and the low half needs its largest value on top. The trick: store each value NEGATED. The smallest negated value is the largest real one, so a min heap of negated values behaves like a max heap. Negate on the way in, negate again on the way out.
For each new value: insert it (negated) into the low heap. Remove the low heap's root and insert it (un-negated) into the high heap, which sends the largest low value across. Then, if the high heap now holds more values than the low heap, move the high heap's smallest value back (negated). After that the low heap's root, un-negated, is the median.
Requirements:
1. Make two heaps with room for count values each: one for the low half (negated values), one for the high half.
2. For each value, in order, do the three moves described above.
3. Then print a line in this form: the words Median after, the value just read, a colon, and the median. For example the line for a value 8 whose median is 5 is Median after 8: 5.
4. Destroy both heaps before returning.
Do NOT write a main function.
Expected Output:
Median after 5: 5 Median after 2: 2 Median after 8: 5 Median after 1: 2 Median after 9: 5
= newline. The output ends with a newline — print one after the last line.
Your Output
Run your code to see the output here...