java - Heap Priority Queue Implementation -
i working on code involving heap implementation , seem getting dereferenced error in bubbleup method, in while loop line. may rather basic question, what's best way solve this? i've had trouble implementing removehigh method, meant remove highest element 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; } }
presumably, once swap element result of parent(index)
change. try
protected void bubbleup() { int index = this.currentsize; int pi; while((pi = parent(index)).compareto(storage[index]) > 0) { swapelement(index, pi); index = pi; } }
Comments
Post a Comment