Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-05-09 PriorityQueue

posted May 9, 2018, 6:16 AM by Konstantinovich Samuel
Priority Queue Class: (estimated work time: 2 days + 1 day to integrate with Maze Solver)

This is a good demo for different pathfinding algorithms:

New Class: Priority Queue.

We will use a heap to store data. The data needs to have a priority associated with it.
Removing by highest/lowest priority will ensure nodes are processed by priority.

Why are we doing this?

By making a frontier that processes nodes by smallest distance, we can make a greedy maze solver!

Best-First Search:
Instead of choosing the 1st node added, or last node added,
Choose the node from the frontier that is closest to the goal.

Lab (extension of the frontier maze solver): 
//Locations need to have an extra field that must be added to the constructor
//This is used in the compareTo() function
public class Location implements Comparable<Location>{
    private double distance;

public class FrontierPriorityQueue implements Frontier{
    //min heap of Locations.
    private MyHeap<Location> data;