Consider a variant of the Log-Structured Merge Tree. It will again be a linked l
ID: 3574851 • Letter: C
Question
Consider a variant of the Log-Structured Merge Tree. It will again be a linked list of arrays, each array is either completely full or completely empty, and each array is sorted. Now, however, the first two arrays will be size 1, the next two will be size 3, the next two will be size 9, etc. That is, arrays 2i and 2i+1 will be of size 3^i.
When we insert into this structure, if the zero'th or first array is empty, we place it in one of those. If both are full, then we do a 3-way merge and place the 3 elements in the second or third array if either is available. If both are full, we again do a 3-way merge and repeat until we find an available array.
For doing the 3-way merge, we use the Merge3 function from the midterm. In other words, you can assume without having to write anything that there is a way to merge 3 sorted arrays of size k into one sorted array of size 3k in time (k).
Answer the following questions. Make sure (as always) to show your work.
Part (a)
What is the worst-case runtime of find(x) for this data structure?
Part (b)
What is the worst-case runtime of insert(x) for this data structure?
Part (c)
What is the amortized worst-case runtime of insert(x) per operation for this data structure? It may help to think about how the contents of this structure correlate to a base-3 number, or you can use a summing approach or a credit scheme.
Explanation / Answer
Hint
// This function takes an array of arrays as an argument and
// All arrays are assumed to be sorted. It merges them together
// and prints the final sorted output.
int *mergeKArrays(int arr[][n], int k)
{
int *output = new int[n*k]; // To store output array
// Create a min heap with k heap nodes. Every heap node
// has first element of an array
MinHeapNode *harr = new MinHeapNode[k];
for (int i = 0; i < k; i++)
{
harr[i].element = arr[i][0]; // Store the first element
harr[i].i = i; // index of array
harr[i].j = 1; // Index of next element to be stored from array
}
MinHeap hp(harr, k); // Create the heap
// Now one by one get the minimum element from min
// heap and replace it with next element of its array
for (int count = 0; count < n*k; count++)
{
// Get the minimum element and store it in output
MinHeapNode root = hp.getMin();
output[count] = root.element;
// Find the next elelement that will replace current
// root of heap. The next element belongs to same
// array as the current root.
if (root.j < n)
{
root.element = arr[root.i][root.j];
root.j += 1;
}
// If root was the last element of its array
else root.element = INT_MAX; //INT_MAX is for infinite
// Replace root with next element of array
hp.replaceMin(root);
}
return output;
}
Time Complexity: The main step is 3rd step, the loop runs n*k times. In every iteration of loop, we call heapify which takes O(Logk) time. Therefore, the time complexity is O(nk Logk).