Hi Dave,
Now I have a better Idea than this.
Dont do anything to K sorted arrays.
Form a heap using all the first elements of the array.
The heap should contain the value of the element and from which array this element is from.
Simply saying heap contains structs which are of the form
typedef struct{
int data;
int indexOfArray;
};
Maintain an index Array of length K.
Now get the root element from the heap add it to the final sorted array. Delete the minimum element from the heap.
Get the next element from the sorted array to which the deleted root element belongs and insert it into the heap.
In the same way keep track of boundary conditions by adding virtual Elements like MAX_INT to the sorted arrays.
regards
Arunachalam.
On 11/28/05, adak <[EMAIL PROTECTED]> wrote:
An example of code using a min heap, if you have it, please. The
previous post of yours I was referring to was this one:
Arunachalam
Jul 13, 10:22 pm show options
From: Arunachalam <[EMAIL PROTECTED]> - Find messages by this
author
Date: Thu, 14 Jul 2005 11:52:53 +0530
Local: Wed, Jul 13 2005 10:22 pm
Subject: Re: [algogeeks] Re: sorting problem
Reply to Author | Forward | Print | Individual Message | Show original
| Report Abuse
Hi,
The solution is to form a Heap of sorted arrays.(Min heap or Max heap)
whether you want the array in ascending order or descending order
resp.
1) Form K Heaps form K sorted arrays.
Total time taken = N
2) Take all the elements from the root node and form a sorted array
keeping track of the index in another array.
3) Now pick the smallest element and put in the result array.
4) Delete the smallest element from that heap and now do a insertion
sort with root of this heap updating the index simultaneously.
5) Keep track of boundary conditions by adding virtual
infinity(MAX_INT) to every heaps and stop processing when you are
adding MAX_INT to the result array.
regards
Arunachalam
Thanks in advance.
Dave
--
===================================
want to know more about me
http"//ww.livejournal.com/users/arunachalam
