Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Min Heap Priority Queue

Posted on 2004-09-30
14
Medium Priority
?
715 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Build and deliver software with DevOps

A digital transformation requires faster time to market, shorter software development lifecycles, and the ability to adapt rapidly to changing customer demands. DevOps provides the solution.

 

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

Build and deliver software with DevOps

A digital transformation requires faster time to market, shorter software development lifecycles, and the ability to adapt rapidly to changing customer demands. DevOps provides the solution.

Question has a verified solution.

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

Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses

704 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