Solved

Min Heap Priority Queue

Posted on 2004-09-30
14
707 Views
Last Modified: 2013-11-23
Hello,

I'm trying to write a nice code for a Min Heap Priority Queue.  I wrote one, but I'm not sure if I implemented the Min Heap Priority Queue correctly, and it seems to only work for Strings right now.  I tried changing it to Objects, then typecasting... but I think I did it wrong.  Anyways, this is the original before the attempted typecasting:

* http://www2.hawaii.edu/~fklam/Java/PriorityQueue.java

Thank you!!

-luna621 =^^=
0
Comment
Question by:luna621
  • 8
  • 6
14 Comments
 
LVL 37

Expert Comment

by:zzynx
ID: 12187655
Hi luna, good to "see" you again ;°)

Your queue works for all types of Comparable objects:

BigDecimal, BigInteger, Byte, ByteBuffer, Character, CharBuffer, Charset, CollationKey, Date, Double, DoubleBuffer, File, Float, FloatBuffer, IntBuffer, Integer, Long, LongBuffer, ObjectStreamField, Short, ShortBuffer, String, URI

What types do you need more?
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12187670
So this works OK:

    public static void main(String[] args) {
        PriorityQueue priorityQ = new PriorityQueue();

        priorityQ.insert( new Integer(10) );
        priorityQ.insert( new Integer(100) );
        priorityQ.insert( new Integer(50) );
        priorityQ.insert( new Integer(1) );

        while (!priorityQ.isEmpty())
            System.out.println(priorityQ.deleteMin());
    }

Of course all elements in the queue should be of the same type
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12187680
If you would mix e.g. String's and Integer's you'll get ClassCastException's in the CompareTo() function
0
Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

 

Author Comment

by:luna621
ID: 12187719
Good to see you again zzynx!!  Missed you from my last question :D

>> String's and Integer's

Darn!  That's what I was going to do after I got this first stage of coding done.  Basically, my idea was to "simulate" the RED algorithm.  I have some datagrams that I'll read in from a, input.txt file with this format:

     Header(String)     Payload(String)     Priority(interger from 0-10)

Example:  

Packet           WowSomethingCool     3
Something     SomethingNotSoCool   10
Another         VeryCool                     0
More             Medium                       5

I'm trying to sort the datagrams through a Priority Queue (where 0 has the highest Priority and 10 has the lowest).
0
 

Author Comment

by:luna621
ID: 12187736
Am I implementing the Min Heap Priority Queue correctly?  I think I am... ^^;
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12187753
>>Darn!  That's what I was going to do after I got this first stage of coding done.
No problem however
Make a class that contains your data and implements the Comparable interface and you're done.

public class MyData implements Comparable {
     private String header;
     private String payLoad;
     private int priority;

     public MyData(String header, String payLoad, int prior) {
         this.header = header;
         this.payLoad = payLoad;
         this.priority = prior;
     }

    public int compareTo(Object obj) {
    }
}
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12187765
>> Am I implementing the Min Heap Priority Queue correctly?
Sorry, don't know that one.

    public int compareTo(Object obj) {
         try {
             MyData data = (MyData)obj;
             if ( priority < data.getPriority() )
               return -1;
             else if ( priority > data.getPriority() )
               return 1;
             else
               return 0;
         } catch (ClassCastException ex) {
            return 0;
         }
    }
0
 

Author Comment

by:luna621
ID: 12187778
Ah ha!!  Okay.  I'll work on that right now.  Might be a while.  If I don't get back to you tonight (or today - is it afternoon for you?), I'll definately post again tomorrow.  Thank you for getting back to me so quickly, as always :D
0
 
LVL 37

Accepted Solution

by:
zzynx earned 500 total points
ID: 12187802
With

/*
 * MyData.java
 *
 */

public class MyData implements Comparable {
        private String header;
        private String payLoad;
        private int priority;

        public MyData(String header, String payLoad, int prior) {
            this.header = header;
            this.payLoad = payLoad;
            this.priority = prior;
        }
       
        public int getPriority() { return priority; }
        public String toString() {
            return header + " - " + payLoad + " - " + priority;
        }

        public int compareTo(Object obj) {
         try {
             MyData data = (MyData)obj;
             if ( priority < data.getPriority() )
               return -1;
             else if ( priority > data.getPriority() )
               return 1;
             else
               return 0;
         } catch (ClassCastException ex) {
            return 0;
         }
        }
}

you can write

public static void main(String[] args) {
        PriorityQueue priorityQ = new PriorityQueue();

        priorityQ.insert( new MyData("Packet", "WowSomethingCool", 3) );
        priorityQ.insert( new MyData("Something", "SomethingNotSoCool", 10) );
        priorityQ.insert( new MyData("Another", "VeryCool", 0) );
        priorityQ.insert( new MyData("More", "Medium" ,5) );

        while (!priorityQ.isEmpty())
            System.out.println(priorityQ.deleteMin());
    }

It nicely prints:

Another - VeryCool - 0
Packet - WowSomethingCool - 3
More - Medium - 5
Something - SomethingNotSoCool - 10

0
 

Author Comment

by:luna621
ID: 12187825
>>        public String toString() {
>>            return header + " - " + payLoad + " - " + priority;
>>        }

I was just about to write that  :D
0
 

Author Comment

by:luna621
ID: 12187845
Okay, I think that's it for now.  I'll have write the RED Algorithm part of the code - that'll take a day or two.  

You don't do SQL, do you?  I'm just starting to learn MS SQL Server 2000 stuff.  Oh well, you can see in my Profile that I asked a bunch of questions already in the SQL section :D

Thank you so much, and hope you have a good day.  Don't worry, I'll probably be back soon :D
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12187853
>> You don't do SQL, do you?
No(t yet :), just the Java TA

>>Thank you so much, and hope you have a good day.
You're welcome. Same for you.
0
 
LVL 37

Expert Comment

by:zzynx
ID: 12187878
Thanks for accepting
0
 

Author Comment

by:luna621
ID: 12187903
No problem :D

I'll post another question if I'm having problems with my RED algorithm implementation :D  Good night!!

-luna621 =^^=
0

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
java.io.BufferedReader   readLine()  //returns the entire file ? 4 73
javap bin 2 34
hibernate example for saving data 19 42
throw exception 21 44
An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question