Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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:

image text in transcribed

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:

image text in transcribed

Our initial step should be sort each chunk one by one, this is doable as we fit each chunk into memory:

image text in transcribed

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

image text in transcribed

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Concepts

Authors: David Kroenke, David Auer, Scott Vandenberg, Robert Yoder

8th Edition

013460153X, 978-0134601533

More Books

Students also viewed these Databases questions

Question

Define Management by exception

Answered: 1 week ago

Question

Explain the importance of staffing in business organisations

Answered: 1 week ago

Question

What are the types of forms of communication ?

Answered: 1 week ago