3
\$\begingroup\$

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<Pair<String, Integer>> heapArray;

public FPPriorityQueue(){
    super();
    heapArray = new ArrayList<Pair<String, Integer>>();
}

public boolean empty(){
    return true;
}

private Integer getParentData(int index){
    int parentIndex = index/2;
    Pair<String, Integer> 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 < childData){
            swap(parentIndex,index);
            shiftUp(parentIndex);
        }
    }
}

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);
            }
        }
    }

}

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);
    }

}

public Pair<String, Integer> removeMax(){

    Pair<String, Integer> returnValue = heapArray.remove(1);
    Collections.swap(heapArray,heapArray.size()-1,1);
    shiftDown(1);

    return returnValue;

}
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the comments! You pointed out some things that I definitely didn't think about. \$\endgroup\$ May 1, 2017 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.