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

x
Solved

# FIFO Minheap Priority Queue

Posted on 2004-11-10
Medium Priority
1,421 Views
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).

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
Question by:luna621
• 14
• 6

LVL 92

Expert Comment

ID: 12552457
welcome back :)

need to see ypur code
0

Author Comment

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

Author Comment

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

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

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

ID: 12573110
0

Author Comment

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

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

Author Comment

ID: 12577101
Located in DataGram.java:

public int compareTo(Object obj) {
try {
DataGram data = (DataGram)obj;
return -1;
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

try {
DataGram data = (DataGram)obj;
return -1;
return 1;
else
return 0;
} // END try
catch (ClassCastException ex) {
return 0;
} // END catch

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

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

Author Comment

ID: 12577104
0

LVL 92

Accepted Solution

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 priority - d.priority;
}

0

Author Comment

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

Author Comment

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

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

ID: 12580894
ve??
0

Author Comment

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

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

sorry for the shorthand :)
0

Author Comment

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

ID: 12580944
0

## Featured Post

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â€¦