Priority Queue Implementation

• 12-20-2011, 10:40 PM
cylus99
Priority Queue Implementation
Hi, I've been given the following assignment to work on...

Implement two versions of Priority Queue Implementation (Insert and bottom up) and determine if one is better than another for large data input.

The heap in question contains the costs of the edges in a minimum spanning tree problem.

I am then meant to go on to use this priority queue to work out a minimum spanning tree of a set of point using kruskals algorithm. As far as my research can tell, insert and bottom up are two ways of building a heap, and I do not understand how these relate to priority queues.

Also, I have so far implemented the insert method, and as you would expect it gives an array so as the heap is a correct heap but the array is not totally sorted which is surely whats required for krukals algorithm?

Anyone got any ideas on what I'm supposed to be doing? Thanks
• 12-20-2011, 11:48 PM
pbrockway2
Re: Priority Queue Implementation
Quote:

As far as my research can tell, insert and bottom up are two ways of building a heap, and I do not understand how these relate to priority queues.
A priority queue is any old data structure that allows (1) elements to be added with a given priority and (2) the highest priority element to be removed. Wikipedia puts it pretty bluntly: "It is a common misconception that a priority queue is a heap. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods".

In Java you might express the relationship between the two by making PriorityQueue an interface. Then you can create two classes which implement this interface, both having a heap at their heart but using the two different methods of heap construction. The Kruskal algorithm can be expressed in terms of the PriorityQueue interface and hence allows for easy comparison.