[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

FIFO Minheap Priority Queue

Posted on 2004-11-10
20
Medium Priority
?
1,421 Views
Last Modified: 2010-05-18
Well, it's been a while.  Nice to be back :D

I've been working this code for a couple days... and it's been giving me some problems.  I originally thought it was working because my input file was small.  But, as the input was more numerous the problem showed itself.  

Here's a break down of what my code is suppose to do:

1. Except data from an input.txt file.
2. Sort according to minheap.
3. Queue according to priority, then by value.
4. Print to output.txt in FIFO order.

What my code actually does:

1. Except data from an input.txt file.
2. Sort according to minheap.
3. Queue according to priority, but only not by value.
4. Prints to output.txt in a strange order (prints the first queued, then starts at the last up).

Please refer to: http://www2.hawaii.edu/~fklam/Java/output.txt

What you are looking at is the output.  I've hardcoded the input for testing purposes:

DG1  aa1  1
DG2  bb2  1
DG3  cc3  1
DG4  dd4  1
               ^ represents priority (1 is the highest, 10 is the smallest), DG_ and _ _# are just Strings.

Each aa, bb, cc, dd will loop 100 times before jumping to the next letter.  

My problem is instead of this output (the one I want):

DG1  aa1  1
DG2  aa2  1
DG3  aa3  1
...
DG1  bb1  1
DG2  bb2  1
DG3  bb3  1
...
DG1  cc1  1
DG2  cc2  1
DG3  cc3  1
...
DG1  dd1  1
DG2  dd2  1
DG3  dd3  1
...

It prints (something slightly off):

DG1  aa1 1  <----- prints correctly
DG100  dd100 1   v----- here down is exact reverse of what I want.
DG99  dd99 1
DG98  dd98 1
...
DG100  cc100 1
DG99  cc99 1
DG98  cc98 1  
...
DG100  bb100 1
DG99  bb99 1
DG98  bb98 1  
...
DG100  aa100 1
DG99  aa99 1
DG98  aa98 1  
...

It prints the first aa1, then it prints the rest in exact reverse order!  Can't figure out what's wrong.  Am I dequeuing it in reverse?  

Other important codes:

1. http://www2.hawaii.edu/~fklam/Java/Output.java
2. http://www2.hawaii.edu/~fklam/Java/PriorityQueue.java
3. http://www2.hawaii.edu/~fklam/Java/DataGram.java

Thank you!!

-luna621 =^^=



0
Comment
Question by:luna621
  • 14
  • 6
20 Comments
 
LVL 92

Expert Comment

by:objects
ID: 12552457
welcome back :)

need to see ypur code
0
 

Author Comment

by:luna621
ID: 12563202
I was trying some testing, but that didn't work:

    private void minHeapify(int i) {
        int l = 2*i;
        int r = (2*i)+1;
        int smallest = -1;

        if ((priorityQ[i]==l) && (priorityQ[i]==r)) {
            if((priorityQ[l] < priorityQ[i]) && (l <= elemNum)) {
                smallest = l;
            } // end if
            else {
                smallest = i;
            } // end else
            if ((priorityQ[r] < priorityQ[smallest]) && (r <= elemNum)) {
                smallest = r;
            } // end if
            if (i != smallest) {
                swap(priorityQ[i], priorityQ[smallest]);
                minHeapify(smallest);
            } // end if
        } // end if
        else {
            if((priorityQ[l] < priorityQ[i]) && (l <= elemNum)) {
                smallest = l;
            } // end if
            else {
                smallest = i;
            } // end else
            if ((priorityQ[r] < priorityQ[smallest]) && (r <= elemNum)) {
                smallest = r;
            } // end if
            if (i != smallest) {
                swap(priorityQ[i], priorityQ[smallest]);
                minHeapify(smallest);
            } // end if
        } // end else
    } // END minHeapify


    private void goDown() {
        int count;
      for(count = (elemNum/2); count > 0; count--) {
          minHeapify(count);
        }
    }
0
Technology Partners: 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: 12571898
Okay, scrap that idea above...

I went through the code again.  I believe it heapifies correctly, but the problem is it doesn't keep track of the order of the elements that are being added.  Maybe that explains the reverse order??
0
 

Author Comment

by:luna621
ID: 12572179
Alrighty, more thinking...

I think I need to add something to the compareTo method that looks at both the priority as well as the header.  Help?
0
 

Author Comment

by:luna621
ID: 12572691
Simple example:

Want to insert: 3a, 2b, 1a, 2a, 1b, 1c, 2c into heap (where the number represents the priority -- 1 is the highest, and
                                                                           the letter represents a key value or "order").

Want the output from the priority queue to look like: 1a, 1b, 1c, 2a, 2b, 2c, 3a.

Question: Do I store in the minheap by order first, then sort by priority in the queue?
0
 

Author Comment

by:luna621
ID: 12575548
Hmm... it sorts the priorities correctly.  But, when the priorities are the same it doesn't sort by the order the element came in - no FIFO.
0
 
LVL 92

Expert Comment

by:objects
ID: 12576170
what does your compareTo() method look like?
0
 

Author Comment

by:luna621
ID: 12577101
Located in DataGram.java:

    public int compareTo(Object obj) {
        try {
            DataGram data = (DataGram)obj;
            if ( header < data.getHeader() && priority < data.getPriority() )
                return -1;
            else if ( header > data.getHeader() && priority > data.getPriority() )
                return 1;
            else if ( priority == data.getPriority() )
                return 1;
            else if ( priority > data.getPriority() )
                return -1;
             else
                 return 0;
        } // END try

        catch (ClassCastException ex) {
            return 0;
        } // END catch

    } // END compareTo


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

    public int compareHeader(Object obj) {  
        try {
            DataGram data = (DataGram)obj;
            if ( header < data.getHeader() )
                return -1;
            else if ( header > data.getHeader() )
                return 1;
             else
                 return 0;
        } // END try
        catch (ClassCastException ex) {
            return 0;
        } // END catch
    } // END compareHeader

-------------------------------------------------------------

I have renamed the goDown method to minHeapify -- but since I did that, it's causing an index out of bounds error.  

These are the current codes: won't run --> no output.txt

1. http://www2.hawaii.edu/~fklam/Java/Output.java
2. http://www2.hawaii.edu/~fklam/Java/PriorityQueue.java
3. http://www2.hawaii.edu/~fklam/Java/DataGram.java



These are the original codes: runs, but sorts in a strange order --> output.txt to verfiy

1. http://www2.hawaii.edu/~fklam/Java/Output.java
2. http://www2.hawaii.edu/~fklam/Java/TestMHPQ.java
3. http://www2.hawaii.edu/~fklam/Java/DataGram.java
4. http://www2.hawaii.edu/~fklam/Java/output.txt
0
 
LVL 92

Accepted Solution

by:
objects earned 2000 total points
ID: 12580779
your compare should be something like:

public int compareTo(Object obj) {
   Datagram d = (Datagram) o;
   if (priority==d.priority) {
      return header - d.header;
   }
   return priority - d.priority;
}

     
0
 

Author Comment

by:luna621
ID: 12580788
Okay, let me try that...
0
 

Author Comment

by:luna621
ID: 12580864
Oh!!  It works!!  But I don't understand what your compareTo method does.  If the priorities were equal, it returns the header - the current header, else priority - current priority.  Could you explain the logic behind that?  Thank you!!!
0
 
LVL 92

Expert Comment

by:objects
ID: 12580880
compareTo() only needs to return a +ve value if greater than, and -ve if less than.
priority - d.priority will be =ve if priority is greater than d.priority etc.

the headers only need to be compared if the priorities are equal, if the priorities are not equal then u only need to compare priorities
0
 

Author Comment

by:luna621
ID: 12580894
ve??
0
 

Author Comment

by:luna621
ID: 12580903
Oh, do you mean and value greater than 0, and value less than 0 and equal 0 if they are equal?
0
 
LVL 92

Expert Comment

by:objects
ID: 12580914
+ve == positive
-ve == negative

sorry for the shorthand :)
0
 

Author Comment

by:luna621
ID: 12580919
Ah ha!  I see now.  Thank you very much for your help!  I'm glad it was just that one portion of my code that needed fixing.  You're a lifesaver!!! :D
0
 
LVL 92

Expert Comment

by:objects
ID: 12580944
Glad I could help :)
0

Featured Post

Technology Partners: 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

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…
In this post we will learn different types of Android Layout and some basics of an Android App.
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…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
Suggested Courses
Course of the Month20 days, 4 hours left to enroll

872 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