Heap Java

/* Implementation of priority Queue. Methods include : add() Top() removeTop() isEmpty() printHeap(); Author : Aravind Ragipindi. */ import java.util.ArrayList; import java.util.Random; class Heap{ private ArrayList myHeap; public Heap(){ myHeap = new ArrayList(); } /* adds the given element to the priority queue. */ public void add(Comparable obj){ myHeap.add(obj); Comparable tmpObj,lastObj = obj; int heapLastIndex = myHeap.size()-1; int lastParent = getParentIndex(heapLastIndex); int i,j = heapLastIndex; for(i = lastParent ; i>=0 && i != j ; i = getParentIndex(i)){ if(lastObj.compareTo(myHeap.get(i))>0){ tmpObj = (Comparable)myHeap.get(i); myHeap.set(i,lastObj); myHeap.set(j,tmpObj); j=i; }else{ break; } } } /* */

returns the parent node's index for any given index. We could check for negative values here before rerturning.

private int getParentIndex(int index){ return (index%2 == 0) ? ( index-2)/2 : (index-1)/2; } /* printHeap() This is for debugging purposes. */

public void printHeap(){ System.out.println(" Elements in Queue are : "); for(int i=0;i<myHeap.size();i++){ System.out.print(" "+myHeap.get(i)); } System.out.println(); } /*

removeTop(); removes and returns the top Node.

*/ public Comparable removeTop(){ Comparable retObj = null; if(!myHeap.isEmpty()){ retObj = (Comparable)myHeap.get(0); Comparable lastObj = (Comparable)myHeap.remove(myHeap.size()-1); if(!myHeap.isEmpty()){ myHeap.set(0,lastObj); } int i = 0; while(i< myHeap.size()){ int maxIndex = getMaxIndex(2*i+1 ,2*i+2); if( maxIndex > 0 && lastObj.compareTo(myHeap.get(maxIndex)) < 0){ Comparable tmpObj = (Comparable)myHeap.get(maxIndex); myHeap.set(maxIndex,lastObj); myHeap.set(i,tmpObj); i = maxIndex; continue; } break; } } return retObj; } /*

just returns the root value or the highest valued node in the priority queue.

*/ public Comparable Top(){ if(!myHeap.isEmpty()) return (Comparable)myHeap.get(0); }

return null;

public boolean isEmpty(){ return myHeap.isEmpty(); } /* private : returns the index value for which the array is holding a higher value among the two given indices. */

private int getMaxIndex(int x,int y){ int retIndex = -1; if(x < myHeap.size() && y < myHeap.size() ) { if(((Comparable)myHeap.get(x)).compareTo((Comparable)myHeap.get(y)) > 0){ retIndex= x; }else{ retIndex = y; } }else if( x >= myHeap.size() && y < myHeap.size() ) { retIndex = y; }else if( x < myHeap.size() && y >= myHeap.size() ) { retIndex= x; } return retIndex; } /*

Now just test for some random values. */ public static void main(String[] args){ Heap pq = new Heap(); Random r = new Random(); for(int i = 0 ; i < 100 ; i++){ pq.add(new Integer(r.nextInt(100))); } pq.printHeap(); System.out.println(" \n Removing elements from priority Queue :"); while(!pq.isEmpty()){ System.out.print(" "+ pq.removeTop()); } System.out.println(); } }