AP exam priority queue

Thread view:

Carol - 30 Jan 2005 23:34 GMT

This relates to the implementation of the priority queue for the AP
computer science exam in Java. How do I implement a priority queue
using linked lists. When an object is added using the enqueue method,
is it then inserted into the linked list in ascending/descending order?
Do you have a sample of code I can look at?

Thanks in advance.

Reply to this Message

Casey Hawthorne - 31 Jan 2005 00:33 GMT

Check "heaps"!

--
Regards,
Casey

Reply to this Message

Chris Smith - 31 Jan 2005 16:48 GMT

> This relates to the implementation of the priority queue for the AP
> computer science exam in Java. How do I implement a priority queue
> using linked lists. When an object is added using the enqueue method,
> is it then inserted into the linked list in ascending/descending order?
> Do you have a sample of code I can look at?

It's fairly simple to implement a priority queue using a
java.util.LinkedList. Simply use a ListIterator to walk through the
list, and call listIterator.add(newObject) when you find the proper
place for the new item.

The data structure is perhaps less than ideal, though; insertion is O(n)
and removal is O(1). Using a heap (a tree with special features),
insertion and removal can both be made O(log n). Faster insertion and
slower removal might seem like a wash, but insertions and removals will
always be equally frequent in the long term. To add AND remove y items
from the queue with about n items in the queue at any given time, the
linked list will take O(y * n), whereas the heap implementation will
take O(y * log n).

Signature

www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

Reply to this Message

AP exam priority queue

Free Magazines