Skip to content

Instantly share code, notes, and snippets.

@rohanraarora
Created November 29, 2015 17:30
Show Gist options
  • Save rohanraarora/c05cf4dba24ee52a427c to your computer and use it in GitHub Desktop.
Save rohanraarora/c05cf4dba24ee52a427c to your computer and use it in GitHub Desktop.
Priority Queue implementation for PuzzeBoard in Puzzle8 game
package com.google.engedu.puzzle8;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.NoSuchElementException;
/**
* Created by Rohan on 11/27/2015.
*/
public class PuzzleBoardPriorityQueue {
private ArrayList<PuzzleBoard> minHeap;
public PuzzleBoardPriorityQueue(){
minHeap = new ArrayList<>();
}
public PuzzleBoard minValue() {
if (minHeap.size() == 0) {
throw new NoSuchElementException();
}
return minHeap.get(0);
}
public void remove() {
PuzzleBoard newValue = minHeap.remove(minHeap.size()-1);
int pos = 0;
if (minHeap.size() > 0) {
while (2*pos+1 < minHeap.size()) {
int minChild = 2*pos+1;
if (2*pos+2 < minHeap.size() &&
minHeap.get(2*pos+2).priority() < minHeap.get(2*pos+1).priority()) {
minChild = 2 * pos +2;
}
if (newValue.priority() > minHeap.get(minChild).priority()) {
minHeap.set(pos, minHeap.get(minChild));
pos = minChild;
}
else {
break;
}
}
minHeap.set(pos, newValue);
}
}
public void addAll(ArrayList<PuzzleBoard> boards){
for(PuzzleBoard board:boards){
add(board);
}
}
public void add(PuzzleBoard puzzleBoard){
minHeap.add(puzzleBoard);
int pos = minHeap.size()-1;
while (pos > 0) {
if (puzzleBoard.priority() < minHeap.get((pos-1)/2).priority()) {
minHeap.set(pos, minHeap.get((pos-1)/2));
pos = (pos-1)/2;
}
else {
break;
}
}
minHeap.set(pos, puzzleBoard);
}
public boolean isEmpty(){
return minHeap.size() <= 0;
}
public PuzzleBoard poll(){
PuzzleBoard min = null;
if(!isEmpty()){
min = minValue();
remove();
}
return min;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment