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
typ
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
Dave,
I did not get which code snippet you need from me.
Can you give me the exact thread link or you want the code snippet for this problem.
regards
Arunachalam.
On 11/23/05, adak <[EMAIL PROTECTED]> wrote:
Hi Arunachalam,I looked up your previous post on min/max heaps. Very interesting
Radix sort.
k is the range of the numbers.
So if i insert a number x, then x is between 0 and k .
0<=x<=k
Hello again, Ed,
I tried my idea - and it didn't work. Unfortunately, if you keep the
array index sorted, (so the binary search can be used), then there's no
advantage, because the index simply matches the subscripts. Meaning
that the array would have to be in sorted order, anyway.
Using a doubl
Hi Arunachalam,
I looked up your previous post on min/max heaps. Very interesting. Do
you have any little snippet of code that I could look at/test, that
would show this algorithm in a small database?
Thanks,
Dave
What is k?
My task is to obtain O(m+k) complexity.
With min heap i will obtain O(m logn). So not to good.
Thanks dave, for your answer.. I'll try :) !
I feel that min heap is the best data structure for this kind of requirement.
Any comments?
regards
Arunachalam.
On 11/22/05, adak <[EMAIL PROTECTED]> wrote:
Yes, you have to re-sort the indexes for every record you add, however,you FIND that index number by a simple binary search (very fast),
Yes, you have to re-sort the indexes for every record you add, however,
you FIND that index number by a simple binary search (very fast), which
you slightly modify for that purpose.
Then, all you need to do is increment each of the current index
numbers, by one, if they are above the number that
I also have to calculate an index, let's say index[i] stores the number
of elements less than i . This thing i have to calculate everytime i
insert a number, so in this way i see it's position. This gives kind of
a bad complexity.. :(
Sort the array by an index number you add to the struct (make it the
first one ). Now, nothing has to be re-sorted, except the index
numbers, and nothing has to be moved around in the array, after it's
been added.
In re-sorting your index's for every new record, remember that the only
index's t
13 matches
Mail list logo
