Max-Heap arraylist based priority queue written in Java

I have a program that I'm writing that needs to use a priority queue as part of an algorithm. I specifically need to order (String, Integer) pairs for example (Bread, 3), (Beer, 5), (Eggs,2), etc.

I'd appreciate any comments on my code style and how I've written my class.

```
import javafx.util.Pair;
import java.util.ArrayList;
import java.util.Collections;

public class FPPriorityQueue implements PriorityQueue {

private ArrayList> heapArray;

public FPPriorityQueue(){
super();
heapArray = new ArrayList>();
}

public boolean empty(){
return true;
}

private Integer getParentData(int index){
int parentIndex = index/2;
Pair parentData = heapArray.get(parentIndex);
return parentData.getValue();
}

private void swap(Integer old, Integer knew){
Collections.swap(heapArray,old,knew);

}

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 (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 rightChildValue){
int leftChildIndex = index*2;
swap(index,leftChildIndex);
shiftDown(leftChildIndex);
}
else{
int rightChildIndex = (index*2)+1;
swap(index,rightChildIndex);
shiftDown(rightChildIndex);
}
}
}

}

public void insert(String key, Integer value){

Pair element = new Pair(key,value);
Pair nullElement = new Pair("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(), eleme

Don't override with the default behavior

private ArrayList> heapArray;

    public FPPriorityQueue(){
        super();
        heapArray = new ArrayList>();
    }

This could be simply

private List> 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 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 element = new Pair(key,value);
    Pair nullElement = new Pair("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 element = new Pair<>(key,value);

    //add the element to the last position in the list
    if (heapArray.isEmpty()) {
        heap.add(new Pair("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("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(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  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();

StackExchange Code Review Q#162187, answer score: 3