mock test

Question

Consider n elements that are equally distributed in k stacks. In each stack, elements of it are arranged in ascending order (min is at the top in each of the stack and then increasing downwards). Given a queue of size n in which we have to put all n elements in increasing order. What will be the time complexity of the best known algorithm?

Comments

it will be O(kn)

rt?

Answer 1

N elements are equally distributed over k Stacks means each stack will have $\left ( \frac{n}{k} \right )$ elements.

Now, apply pop operation to get top element from each stack and construct Min Heap.

we will have k elements from each stack and time complexity to construct Min heap will be $O(k)$.

Now apply deletion to root node and insert it into Queue and Heapify remaining heap and repeat this procedure untill we remove all elements from heap. This operation with heapify operation will take total of time $O(k log k)$.

So, now we have k sorted elements in Queue.

we have to repeat this whole procedure $\left ( \frac{n}{k} \right )$ times because in each step we have k elements from each stack.

so Total time complexity will be $= \left ( \frac{n}{k} \right ) \cdot (klogk) = n log k$.

Comments

stacks elemeny are already sorted. cant we apply merge procedure over stacks?

---

why can't we use k way merge sort?
There we will have n/k elements in each stack which is sorted. To merge them we will need
 ( n/k) * k = O(n) , isn't it?

---

how can you do such a procedure 

say stack 1 contains 

1

2

3

4

stack 2 contains 

100

101

102

103

stack 4 contains

2000

2001

2002

2003

2004

• if u now pop top elements of s1 s2 s3 these are 1,100,2000 clearly a min heap so according to your algorithm we insert 1,100,2000 in queue
• now during 2^nd pop 2,101,2001 are popped up, clearly again a min-heap now insert 2,101,2001 into queue 
• and so on 

now queue contains     …... 2001,101,2,2000,100,1

clearly its not increasing order of elements 

correct me if I am wrong

---

I have same doubt as @musa…. how can we gaurantee that always sorting among the tops of the stacks gives all n elements sorted order. Because its nowehere given in the question that stacks top have first min elements always

Answer 2

The algorithm should be like this

• All k stacks contain k pointer
• k pointers are pointing to the top element of the stack
• Now, all these elements are compared and the smallest one is popped and put inside the queue
• Now, which stack is popped one element, it points to the second element of that stack, and all other stack points to the first elements to the stack
• Again comparison done with the top element of the stack
• Like this all kn elements are compared and pushed into the queue

So, time complexity will be O(kn)

Comments

@srestha.

yours is a naive approach.

1)let us construct a min heap with all the top elements of k stacks.==>O(k)

2)extract min and add it to queue, then insert the next element of stack into min heap ==>O(logk)+O(1)+O(logk)

so total n extract-mins,n insertions into queue, n-k insertions into min heap.

total complexity: O(k)+O(nlogk)+O(n)+O((n-k)*logk)

i.e O(nlogk)

is my approach correct?

---

yes rt

---

@srestha why can't we use k way merge sort?
There we will have n/k elements in each stack which is sorted. To merge them we will need
 ( n/k) * k = O(n) , isn't it?

---

marging in O(k)??

is it possible?

---

Suppose, there are 2 stacks - Stack 1 containing the elements {2, 6 and 8} and Stack 2 containing the elements {7, 9 and 11}. Does the above algorithm work then?

Because, the min heap (or for that matter any other data structure), will contain the elements {2 and 7} in the 1st round. But then, this will put 2, and then 7 into the queue. 6 will come later. The approach might fail.

Answer 3

1)let us construct a min heap with all the top elements of k stacks.==>O(k)

2)extract min and add it to queue, then insert the next element of stack into min heap ==>O(logk)+O(1)+O(logk)

so total n extract-mins,n insertions into queue, n-k insertions into min heap.

total complexity: O(k)+O(nlogk)+O(n)+O((n-k)*logk)

i.e O(nlogk)