Java BinaryHeap not working on A* (not sorted)

I am using this implementation of Heap for A* algorithm:

https://courses.cs.washington.edu/courses/cse373/11wi/homework/5/BinaryHeap.java

I slightly modified it but only adding contains method and renaming remove to poll, because I previously used PriorityQueue but it didn’t work.

Here is my implementation of Comparable<Spot> interface:

@Override
public int compareTo(Spot o) {
    Double.compare(getF(), o.getF());
}

getF() returns double…

however when I print the Heap with all the getF()s I see this:

1. 176.0
2. 175.0
3. 180.0
4. 176.0
5. 223.0
6. 182.0
7. 146.0
8. 177.0
9. 87.0
10. 202.0
...

Now the 175 is wrong because it’s lower than 176, 87 is also wrong…

The same exact thing happened to me with PriorityQueue, what am I doing wrong?

EDIT
Here is my A* implementation:

public List<Spot> process(GameBodyObject me, Point target, ArrayList<GameBodyObject> others) throws Exception {

    if(grid == null) {
        throw new Exception("You have to initialize AStar first.");
    }

    grid.unsetObstacleForObject(me);

    Spot start = grid.getSpotAtPosition(me.getPosition().getX(), me.getPosition().getY());
    Spot end = grid.getSpotAtPosition(target.getX(), target.getY());

    end = grid.moveSpotSoThatItDoesntCollide(end, me.getRadius());

    Heap<Spot> openSet = new Heap<Spot>(grid.getMaxSize());
    List<Spot> closedSet = new ArrayList<>();
    List<Spot> path = new ArrayList<>();

    openSet.add(start);

    while(openSet.size() > 0) {

        /*int winner = 0;
        for(int i = 1; i < openSet.size(); i++) {
            if(openSet.get(i).getF() < openSet.get(winner).getF()) {
                winner = i;
            }
        }*/

        Spot current = openSet.poll(); //openSet.get(winner);

        int i = 1;
        for(Spot s : Arrays.asList(openSet.getArray())) {
            if(s != null) {
                System.out.println(i + ". " + s.getF());
                i++;
            }
        }

        if(current.equals(end)) {
            // We are done, reconstruct the path...
            Spot temp = current;
            path.add(temp);
            while(temp.getPrevious() != null) {
                path.add(temp.getPrevious());
                temp = temp.getPrevious();
            }

            grid.resetObstacles();
            return path;
        }

        closedSet.add(current);

        List<Spot> neighbors = current.getNeighbors();

        for(Spot neighbor : neighbors) {
            if(!closedSet.contains(neighbor) && !grid.isCollidingWithObstacle(neighbor, me.getRadius())) {
                double tempG = current.getG() + 1;
                if(openSet.contains(neighbor)) {
                    if(tempG < neighbor.getG()) {
                        neighbor.setG(tempG);
                    }
                } else {
                    neighbor.setG(tempG);
                    openSet.add(neighbor);
                }

                neighbor.setH(heuristic(neighbor, end));
                neighbor.setF(neighbor.getG() + neighbor.getH());
                neighbor.setPrevious(current);
            }
        }

    }

    grid.resetObstacles();
    return new ArrayList<>();
}

A common problem when using Java’s PriorityQueue or similar heap implementations to implement Dijkstra or A* algorithms is the missing of a decreaseKey method. Both Dijkstra or A* sometimes need to change the priority of an element inserted into the Heap. The only way to circumvent the missing of this functionality is to remove the element (which is slow in Java’s PriorityQueue implementation) and then re-insert it.

But there is one problem with this: When removing the object from the PQ/Heap, it must still contain the “old” priority (getF() must still return the old value in your case), as otherwise the element may not be found. If the element already contains the new value, the PQ/Heap would look for it in the new place to be removed, instead of in the place matching the old value.

So, the sequence must be: (1) remove element from PQ, (2) adapt its weight/priority, (3) re-insert it into the PQ.

In your code, you have the following part:

            if(openSet.contains(neighbor)) {
                if(tempG < neighbor.getG()) {
                    neighbor.setG(tempG); // *1
                }
            } else {
                neighbor.setG(tempG);
                openSet.add(neighbor);
            }

            neighbor.setH(heuristic(neighbor, end));
            neighbor.setF(neighbor.getG() + neighbor.getH()); // *2
            neighbor.setPrevious(current);

If you look closely at it, you modify the weight of neighbor at line marked *2 due to the change at line *1. To fix it, you could try the following:

            if(openSet.contains(neighbor)) {
                if(tempG < neighbor.getG()) {
                    openset.remove(neighbor); // *3
                    neighbor.setG(tempG);
                }
            } else {
                neighbor.setG(tempG);
                // openSet.add(neighbor); // *4
            }

            neighbor.setH(heuristic(neighbor, end));
            neighbor.setF(neighbor.getG() + neighbor.getH());
            openSet.add(neighbor); // *5
            neighbor.setPrevious(current);

This removes the element from the Heap if it’s already there (*3) and inserts it only after the weight is correctly calculated (*4, *5).

The problem now: Your Heap-implementation does not offer such a remove(Object) method. Java’s PriorityQueue does. So you would have to change to Java’s PriorityQueue, or to another Heap-Implementation that offers a remove(Object) method. (Or even better: a decreaseKey method, so one would not have to remove an re-insert the element at all).

In many Dijkstra/A*-Implementations I saw using Java’s PQ, this was done wrong in the first attempt, leading to the incorrect order of the Heap.

tl;dr: Do not modify the weight/priority of an element already inserted into a PriorityQueue or Heap.