Heap Java

  • October 2019
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Heap Java as PDF for free.

More details

  • Words: 378
  • Pages: 3
/* 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(); } }

Related Documents

Heap Java
October 2019 18
Heap
May 2020 9
Heap Sort
May 2020 9
Fibonacci Heap
May 2020 5
Heap Sort
November 2019 15
Heap Sort
April 2020 24