Created
November 29, 2015 17:30
-
-
Save rohanraarora/c05cf4dba24ee52a427c to your computer and use it in GitHub Desktop.
Priority Queue implementation for PuzzeBoard in Puzzle8 game
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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