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
