Min Heap Priority Queue

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 =^^=
luna621Asked:
Who is Participating?
 
zzynxConnect With a Mentor Software engineerCommented:
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
 
zzynxSoftware engineerCommented:
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
 
zzynxSoftware engineerCommented:
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
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
zzynxSoftware engineerCommented:
If you would mix e.g. String's and Integer's you'll get ClassCastException's in the CompareTo() function
0
 
luna621Author Commented:
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
 
luna621Author Commented:
Am I implementing the Min Heap Priority Queue correctly?  I think I am... ^^;
0
 
zzynxSoftware engineerCommented:
>>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
 
zzynxSoftware engineerCommented:
>> 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
 
luna621Author Commented:
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
 
luna621Author Commented:
>>        public String toString() {
>>            return header + " - " + payLoad + " - " + priority;
>>        }

I was just about to write that  :D
0
 
luna621Author Commented:
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
 
zzynxSoftware engineerCommented:
>> 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
 
zzynxSoftware engineerCommented:
Thanks for accepting
0
 
luna621Author Commented:
No problem :D

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

-luna621 =^^=
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.