Question
Provide a visual diagram and a brief description of merging the next three iterations. Include your answer to the question posed in the project description:
Provide a visual diagram and a brief description of merging the next three iterations. Include your answer to the question posed in the project description: Question: Why don't we take all of values in heap (1, 8, 11) here? What is the problem in that case?
Example approach:
Lets try our approach with an example. Assume we have the following input file data:
Let's assume our memory can keep 3 items, in this case our chunks must be 3 items at max so that they can be kept in memory, so:
Our initial step should be sort each chunk one by one, this is doable as we fit each chunk into memory:
Now we need to merge those chunks, but remember our memory space is limited, we cannot even keep 1 per chunk, what would require 15 items, which is > 3.
Here we need to change our way of thinking, remember that we need the "3 smallest items" of those 15 items. If it's higher than those items, we remove it from the heap and return it to the chunk it belongs to.
Note: This is just one of the possible approaches, you can have a different approach.
Our heap: empty to begin with.
Get 20 from file-1-chunk-1 (20, 44, 62)
do we need to add this item to heap? Yes, heap has capacity, then add to heap, heap includes 20
do we need to remove an item from heap? No (since our heap has 1 item)
Get 11 from file-1-chunk-2 (11, 43, 61)
do we need to add this item to heap? Yes, heap has capacity, then add to heap, heap includes 11, 20
do we need to remove an item from heap? No (since our heap has 2 items)
Get 65 from file-1-chunk-3 (65, 72, 76)
do we need to add this item to heap? Yes, heap has capacity, then add to heap, heap includes 11, 20, 65
do we need to remove an item from heap? No (since our heap has 2 items)
Get 94 from file-1-chunk-4 (94)
do we need to add this item to heap? No, heap has no capacity AND it is bigger than the maximum value in heap (i.e. 65)
Get 40 from file-2-chunk-1 (40, 60, 70)
do we need to add this item to heap? Yes, heap has no capacity BUT it is smaller than the maximum value in heap (i.e. 65)
do we need to remove an item from heap? Yes, we are at capacity, so remove 65 put is back to from file-1-chunk-3 (you already remember that this value is from file-1-chunk-3, right?), our heap becomes (11, 20, 40)
Get 20 from file-2-chunk-2: (20, 38, 82)
Our heap becomes (11, 20, 20), we return 40 the chunk it belongs to
After we check all chunks in this manner (15 chunks) until we are satisfied that we have all the minimums, our heap should be (1, 8, 11). We take the minimum value from this heap (1) and pass to output.
Question: Why don't we take all of values in heap (1, 8, 11) here? What is the problem in that case? Include your answer in this week's weekly discussion.
Our output becomes: 1
Note: Please note the difference in the chunks compared to the initial status.
Now we start the merge again, just like before.
numbers01.txt numbers02.txt 00 numbers03.txt numbers04.txt 20, 62, 44, 11, 61, 43, 76, 65, 72, 94 40, 70, 60, 38, 20, 82, 83, 82, 84 11, 47, 51, 44, 21, 57, 59, 99, 57, 3, 86, 1, 94, 95, 73, 75, 67, 26, 18, 37Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started