Don't override with the default behavior
private ArrayList<Pair<String, Integer>> heapArray;
public FPPriorityQueue(){
super();
heapArray = new ArrayList<Pair<String, Integer>>();
}
This could be simply
private List<Pair<String, Integer>> heap = new ArrayList<>();
You don't need a custom constructor. This will declare and initialize it.
I prefer the name heap to heapArray. It's simpler and more accurate.
In the latest Java, you don't have to specify Pair<String, Integer> twice. It's smart enough to figure it out if you just say <>.
In general, it is preferable to use interfaces as types rather than implementations. Among other reasons, it allows you to change implementations easily.
Huh?
public boolean empty(){
return true;
}
What's this do? If it was called isEmpty, I'd think it was returning whether or not the heap was empty. As is, I would expect empty to do something, perhaps clear the heap.
Whatever it's supposed to do, it doesn't seem to be doing it.
Don't rely on your inputs
private void shiftUp(int index){
int parentIndex;
if(index != 1){
parentIndex = index/2;
int childData = heapArray.get(index).getValue();
int parentData = getParentData(index);
if(parentData < childData){
swap(parentIndex,index);
shiftUp(parentIndex);
}
}
}
What if index is less than 1?
private void shiftUp(int index) {
if (index > 1) {
int parentIndex = index / 2;
int parentData = heap.get(parentIndex).getValue();
int childData = heap.get(index).getValue();
if (parentData < childData) {
swap(parentIndex, index);
shiftUp(parentIndex);
}
}
}
Changing != to > handles index values less than 1. And it's free. We're already doing a comparison. Why not do the better one?
We don't need getParentData. We have to calculate parentIndex anyway, so we can just fetch directly.
I added some extra whitespace, because I find code easier to read that way.
Don't do unnecessary work
public void insert(String key, Integer value){
Pair<String, Integer> element = new Pair<String, Integer>(key,value);
Pair<String, Integer> nullElement = new Pair<String, Integer>("NULL",0);
//add the element to the last position in the list
if(heapArray.isEmpty()){
heapArray.add(0,nullElement);
heapArray.add(1,element);
}
else{
heapArray.add(heapArray.size(), element);
shiftUp(heapArray.size()-1);
}
}
We don't need nullElement every time. Consider
public void insert(String key, Integer value) {
Pair<String, Integer> element = new Pair<>(key,value);
//add the element to the last position in the list
if (heapArray.isEmpty()) {
heap.add(new Pair<String, Integer>("NULL", 0));
heap.add(element);
} else {
heap.add(element);
shiftUp(heap.size()-1);
}
}
We don't have to explicitly say that we want to put things in the last position. That's how the single argument add works already.
I personally am not crazy about the half-cuddled else {, and it's not the Java standard. So I fully cuddled: } else {.
We only create nullElement in the one edge case now. The rest of the time, we don't bother. But we can actually do better. Consider
public FPPriorityQueue() {
heap.add(new Pair<String, Integer>("NULL", 0));
}
This will create the null element the one time you need it, at the beginning. And this is the kind of thing that you do in a constructor.
You don't need the explicit super(). Java's smart enough to do that for you when you're just calling the default constructor.
Now we can just say
public void insert(String key, Integer value) {
//add the element to the last position in the list
heap.add(new Pair<String, Integer>(key, value));
shiftUp(heap.size() - 1);
}
It adds to the end of the list.
And because we previously changed shiftUp to handle the empty case, we don't need to prevent calling shiftUp in that case.
I'm not sure that we need the null element. The math is a little more complex without it but still doable.
Don't Repeat Yourself
private void shiftDown(int index){
if(heapArray.size()> (index*2)+1) {
int leftChildValue = heapArray.get(index * 2).getValue();
int rightChildValue = heapArray.get((index * 2) + 1).getValue();
int indexValue = heapArray.get(index).getValue();
if(indexValue < leftChildValue || indexValue < rightChildValue)
{
if(leftChildValue > rightChildValue){
int leftChildIndex = index*2;
swap(index,leftChildIndex);
shiftDown(leftChildIndex);
}
else{
int rightChildIndex = (index*2)+1;
swap(index,rightChildIndex);
shiftDown(rightChildIndex);
}
}
}
}
Consider
private void shiftDown(int index) {
int left = index * 2;
int right = left + 1;
if (heap.size() > right) {
int leftChildValue = heap.get(left).getValue();
int rightChildValue = heap.get(right).getValue();
int indexValue = heap.get(index).getValue();
if (indexValue < leftChildValue || indexValue < rightChildValue) {
if (leftChildValue > rightChildValue) {
swap(index, left);
shiftDown(left);
} else {
swap(index, right);
shiftDown(right);
}
}
}
}
This way we set left and right before using them. So we can't accidentally pick the wrong value one place.
Don't reinvent the wheel
If this is an exercise to improve your understanding of how a heap works, that's fine. There's a reinvent-the-wheel tag that you can use to let us know. But if you just needed to solve the problem, an easier way is to use a PriorityQueue with a custom Comparator or a custom type that extends Comparable. Then Java will handle all the fiddly bits of managing the heap.
public class PairComparator implements Comparator<Pair<String, Integer>> {
public int compare(Pair<String, Integer> a, Pair<String, Integer> b) {
return b.getValue().compareTo(a.getValue());
}
}
If the order is backwards, switch a and b in the return line.
I forget if you have to implement equals as well.
You'd use this like
PriorityQueue<Pair<String, Integer>> queue = new PriorityQueue<>(new PairComparator());
Then you can call queue.add and queue.poll to insert and remove items.
You don't provide test code, so I haven't tried to compile and test any of this. Beware of typos, etc.
