I have been working on a C# calendar queue data structure as defined in the
paper:
http://www.leekillough.com/heaps/pap...dar_queues.pdf
I am hoping someone can recommend how they would approach the following,
which is simplified for illustration:
public class CalendarQueue
{
private SortedLinkList[] buckets
public void Enqueue(Object obj);
public Object DequeueMin()
private void Resize(int newSize)
}
Basically, when you enqueue objects into the CalendarQueue, the object will
be placed into one bucket within the buckets. Each bucket is a
SortedLinkList. The end result is that each bucket will have a different
amount of objects. The buckets are sorted and the objects within each
bucket is sorted.
The CalendarQueue is smart enough to keep track of the cost of enqueueing
and dequeueing. When enqueueing and dequeueing get too costly, the
CalendarQueue will Resize itself.
Resizing code is where my question is. Resizing potentially could double
the number of buckets. When more buckets are added, the objects in the
previous buckets will need to be placed into the new set of buckets. What
is the most optimal way of doing this in C#?
The pdf file was created with C code. It recommends having a very big array
where the buckets will swap back and forth from top of the array to the
bottom. For example, lets say the big array has 1000 capacity and the
current buckets is 100. Buckets will occupy 0-100 of the big array and then
when resized to 200, buckets will occupy 800-1000. The object will have to
move from the 0-100 buckets to the 800-1000 bucket. Most likely, each new
bucket will contain about half as many objects in the new set.
How would you approach this issue of moving objects in one SortedLinkList
into another SortedLinkList as fast as possible?
This has been a fun exercise and cant wait to hear what you guys think.
Sincerely,
Dan
