Results 1 to 2 of 2
  1. #1
    cylus99 is offline Member
    Join Date
    Dec 2011
    Posts
    1
    Rep Power
    0

    Default 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

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default Re: Priority Queue Implementation

    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.

Similar Threads

  1. Priority Queue
    By fam2315 in forum New To Java
    Replies: 5
    Last Post: 06-29-2011, 03:10 AM
  2. Priority Queue with explicit priority
    By lsk in forum Advanced Java
    Replies: 4
    Last Post: 06-10-2011, 07:16 PM
  3. Priority Queue
    By Suende in forum New To Java
    Replies: 19
    Last Post: 04-25-2011, 08:46 AM
  4. Priority Queue Question
    By Taz_84 in forum New To Java
    Replies: 0
    Last Post: 01-29-2009, 03:23 AM
  5. How to implement Priority queue with Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:49 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •