Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Min Heap Priority Queue

Posted on 2004-09-30
14
Medium Priority
?
719 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

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 2000 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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Suggested Courses

824 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