Solved

Min Heap Priority Queue

Posted on 2004-09-30
14
710 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
running on tomcat not jboss eap 7.0 3 28
batch vs regular insert in spring DAO 2 20
Java array 21 77
Java Inheritance super keyword use 8 30
Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

685 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