Heap Priority Queue Implementation

Question

I am working on a code involving a Heap implementation and I seem to be getting a dereferenced error in my bubbleUp method, in my while loop line. This may be a rather basic question, but what's the best way to solve this? I've also had some trouble implementing the removeHigh method, which is meant to remove the highest element from the queue.

public class HeapPriorityQueue implements PriorityQueue 
{
    protected final static int DEFAULT_SIZE = 10000;

    protected Comparable[] storage;
    protected int currentSize;

    public HeapPriorityQueue () 
    {
        this.storage=new Comparable[DEFAULT_SIZE];
        this.currentSize=0;
    }

    public HeapPriorityQueue(int size)
    {
        this.currentSize=size;
        this.storage=new Comparable[currentSize];
    }

    public int size ()
    {
        return currentSize;
    }

    public boolean isEmpty ( )
    {
        if(currentSize==0)
            return true;
        else
            return false;
    }

    public boolean isFull ( )
    {
        if(currentSize==DEFAULT_SIZE)
            return true;
        else
            return false;
    }

    public Comparable removeHigh () throws HeapEmptyException
    {
        if(isEmpty()) {
            throw new HeapEmptyException();
        }else{
            Comparable[] k = new Comparable[0];
            k.equals(storage[1]);
            storage[1] = storage[currentSize];
            storage[currentSize] = null;
            currentSize--;
            bubbleDown();
            return storage[currentSize];
        }
    }

    public void insert ( Comparable k  ) throws HeapFullException
    {   
        if(isFull()) {
            throw new HeapFullException();
        }
            currentSize++;
            int index = currentSize;
            storage[index] = k;

            bubbleUp();

    }

    protected void bubbleUp ( ) 
    {
        int index = this.currentSize;

        while(parent(index).compareTo(storage[index]) > 0) {
            swapElement(index, parent(index));
            index = parent(index);
        }

    }

    protected void bubbleDown() 
    {
        int index = 1; 
        while (hasLeft(index)) {
            int smaller = leftChild(index);

            if(hasRight(index) && 
                storage[leftChild(index)].compareTo(storage[rightChild(index)])>0) {
                    smaller = rightChild(index);
                }

            if(storage[index].compareTo(storage[smaller]) > 0) {
                swapElement(index, smaller);
            }else{
                break;
            }
        }


    }   

    protected void swapElement ( int p1, int p2 )
    {
        Comparable k = storage[p1];
        storage[p1] = storage[p2];
        storage[p2] = k;

    }

    protected int parent ( int pos )
    {
        if(pos>1)
            return pos;
        else
            return 0;
    }

    protected int leftChild ( int pos )
    {
        return pos*2;
    }

    protected int rightChild ( int pos )
    {   
        return pos*2+1;
    }

    protected boolean hasLeft ( int pos )
    {
        if(leftChild(pos) <= currentSize)
            return true;
        else
            return false;
    }

    protected boolean hasRight ( int pos )
    {
        if(rightChild(pos) <= currentSize)
            return true;
        else
            return false;
    }


}

Elliott Frisch · Accepted Answer · 2014-12-02 04:43:31Z

1

Presumably, once you swap the element the result of parent(index) will change. Try

protected void bubbleUp() {
    int index = this.currentSize;
    int pi;
    while((pi = parent(index)).compareTo(storage[index]) > 0) {
        swapElement(index, pi);
        index = pi;
    }
}

answered Dec 2, 2014 at 4:43

Elliott Frisch

202k20 gold badges165 silver badges265 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Heap Priority Queue Implementation

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related