Provide a visual diagram and a brief description of merging the next three itera

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: 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, 37

Explanation / Answer

We do not take all the items [1, 8, 11], because in order to arrive at this heap, we have just considered the BIGGEST number from the HEAP on every PHASE/PARSE to be knocked-out with an incoming smallest number froma CHUNK. Remember that from EACH chunk, we had picked up the SMALLEST number to knock out the BIGGEST number from the HEAP. So, there are cases where the CHUNK had two numbers small enough to have knocked out TWO big numbers from the HEAP.

For example, one CHUNK had [3, 86, 1]. While we took 1 from that chunk and moved on to the next CHUNK, without reparsing the same CHUNK again until all the BIGGER ones from the HEAP had been knocked-out by the smaller ones from the CHUNK.

Thus, taking (1, 8, 11) as the first 3 smallest-values will be incorrect.

Thus multiple cycles will be needed to start the merge again for the next lowest number or multiple parsing per chunk wil be required in each merge cycle.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.