asked on

FIFO Minheap Priority Queue

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 =^^=

Mick Barry

welcome back :)

need to see ypur code

luna621

ASKER

Links are listed above, but here they are again :D

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

And this is the output: http://www2.hawaii.edu/~fklam/Java/output.txt

luna621

ASKER

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);
}
}

luna621

ASKER

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

luna621

ASKER

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?

luna621

ASKER

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?

luna621

ASKER

Updated codes:

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

And this is the output: http://www2.hawaii.edu/~fklam/Java/output.txt

luna621

ASKER

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.

Mick Barry

what does your compareTo() method look like?

luna621

ASKER

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

luna621

ASKER

Whoops!

Originals are located here:

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

ASKER CERTIFIED SOLUTION

Mick Barry

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

luna621

ASKER

Okay, let me try that...

luna621

ASKER

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

Mick Barry

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

luna621

ASKER

ve??

luna621

ASKER

Oh, do you mean and value greater than 0, and value less than 0 and equal 0 if they are equal?

Mick Barry

+ve == positive
-ve == negative

sorry for the shorthand :)

luna621

ASKER

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

Mick Barry

Glad I could help :)