Various praise/comments/rants about Troy, RPI, PhDs, Macs, and life in general.

Thursday, July 17, 2008

Cocoa / Objective-C Priority Queue

K - one more problem. For my project, I was looking for a quick Objective-C or Cocoa priority queue implementation. You'd think they'd have one, but no. I tried googling, and I did find some stuff, but everything was zip files you had to download to open. Too much of a pain in the ass for me. So I broke open the CLRS book to find priority queues. Here's my quick implementation of a priority queue in Cocoa / Objective-C.


-(id)init
{
[super init];
q = [[NSMutableArray alloc] init];
return self;
}

- (void)insertEvent:(Event *)item
{
int index;

[q addObject:item];

index = [q count] - 1;

// Maintain heap-ness
while(YES) {
if([q objectAtIndex:index] < [q objectAtIndex:((index - 1)/ 2)]) {
[q exchangeObjectAtIndex:index withObjectAtIndex:((index - 1)/ 2)];
index = (index - 1)/ 2;
}
else
break;
}
}

- (id)getNextEvent
{
// Exchange the first element with the last element to save
// the cost of moving them all forward and then re-heaping it
Event *e;

int size;

size = [q count];

if(size == 0)
return nil;

[q exchangeObjectAtIndex:0 withObjectAtIndex:(size - 1)];
e = [[q objectAtIndex:(size - 1)] retain];

[q removeLastObject];

// Now one of 0 or 1 are the next min...
// If there are 0 or 1
[self heapify:0];
// Do the update to maintain heap property
return e;
}

- (void)heapify:(int)i
{
int left, right;
int min;
int max_index = [q count] - 1;

left = 2 * i + 1;
right = 2 * i + 2;

if(left < max_index && [q objectAtIndex:left] < [q objectAtIndex:i]) {
min = left;
}
else
{
min = i;
}

if(right < max_index && [q objectAtIndex:right] < [q objectAtIndex:min]) {
min = right;
}

if(min != i) {
[q exchangeObjectAtIndex:i withObjectAtIndex:min];
[self heapify:min];
}
}


Hopefully I didn't make any mistakes - I modified this slightly from my code because there was a little more stuff in my priority queue than I put here, but overall, it should be enough to get you started.

As an aside, priority queues are really neat and are a clear example of the usefulness of analysis and big-oh notation. For example, insertEvent is O(log n), getNextEvent is O(1) but it calls heapify which is O(log n). So actually any operation you do on a priority queue is an O(log n) operation - a very attractive property.

I could have used this priority queue implementation but I would have had to download a .zip file which is a pain in the ass. This guy left it as an exercise to the reader which is nice but didn't help me much. So... here's my solution. Let me know if it helps and for God's sakes if there's any bugs PLEASE let me know! Thanks.

10 comments:

Jens Alfke said...

(Why is downloading a .zip file a pain? You click a link, you (optionally) double-click the .zip file if Safari didn't auto-expand it, and voila, there's the code. Personally, I would find it more of a pain to have to find my copy of Sedgewick and look up priority queues in the index.)

There's a problem with your code, by the way. You're trying to compare the objects using the C "<" operator. That won't do what you want. As in C, it compares the pointers. So instead of telling you which Event is smaller, it just tells you which object has a lower memory address.

What you want to do instead is call the standard method "compare:" on the two objects. Presumably your Event class would implement that method to return the right comparison result (-1, 0 or 1).

laprej said...

It's just a pain because maybe I just want to look at code really quickly instead of having to download the .zip file, unzip it, sort through the multiple files that came in the .zip... You get the idea :) Plus I'm very hesitant to download things as my Downloads folder has grown insanely huge!

But yeah, that would be a bug, but actually I do something different in my code... In the *actual* code I do something like this:

if([[q objectAtIndex:index] timestamp] < [[q objectAtIndex:((index - 1)/ 2)] timestamp]) {...

So I actually compare the timestamp member of my Event class which is just a double. I pulled that out of the code I posted, though, because it's specific to discrete event simulators. In hindsight, though, maybe I should have just posted my unmodified code...

But yes, you are right in that using the plain old less than operator often won't Do The Right Thing [tm]. Good catch!

viagra online said...

That won't do what you want. As in C, it compares the pointers. So instead of telling you which Event is smaller, it just tells you which object has a lower memory address.

Anonymous said...

very nice!

Anonymous said...

Small mistake variable "max_index" should be [q count].

Anonymous said...

I would like to exchange links with your site www.blogger.com
Is this possible?

Kansas City Attractions said...

amazing and very inspiring. When you get a chance, please check out my article. Thanks for sharing information.

Viagra said...

I cannot see any mistake in this!

Anonymous said...
This comment has been removed by a blog administrator.
Tramadol said...

Great website, continue the Excellent work!