com.limegroup.gnutella.util
Class BinaryHeap

java.lang.Object
  extended bycom.limegroup.gnutella.util.BinaryHeap

public class BinaryHeap
extends java.lang.Object

A class for maintaining the objects in a binary heap form, i.e., a classic fixed-size priority queue. Its a MAX heap, i.e., the root of the heap is the element with max value. The objects to be inserted into the heap must implement java.lang.Comparable interface, as that is what is used for comparison purposes so as to order the objects in the heap form. While in the heap, these objects must not be mutated in a way that affects compareTo. This class is not synchronized; that is up to the user.

BinaryHeap now contains a constructor to allow dynamic resizing as well.

See Also:
FixedsizePriorityQueueTest

Constructor Summary
BinaryHeap(java.lang.Comparable[] array)
          Initializes the array with the passed array Also takes the length of the array and sets it as the currentSize as well as maxSize for the heap, and makes heap out of that.
BinaryHeap(int maxSize)
          Constructs a new fixed-size BinaryHeap.
BinaryHeap(int maxSize, boolean resizable)
          Constructs a new BinaryHeap to initially hold the given number of elements.
 
Method Summary
 int capacity()
          Returns the maximum number of elements in this without growing the heap.
 void clear()
           
 java.lang.Comparable extractMax()
           
 java.lang.Comparable getMax()
          Returns the largest element in this, without modifying this.
 java.lang.Comparable insert(java.lang.Comparable x)
           
 boolean isEmpty()
          Returns true if this is empty, i.e., size()==0
 boolean isFull()
          Returns true if this cannot store any more elements without growing the heap, i.e., size()==capacity().
 java.util.Iterator iterator()
           
 int size()
          Returns the number of elements in this.
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

BinaryHeap

public BinaryHeap(int maxSize)
Constructs a new fixed-size BinaryHeap.


BinaryHeap

public BinaryHeap(int maxSize,
                  boolean resizable)
Constructs a new BinaryHeap to initially hold the given number of elements. Iff resize is true, the heap will grow dynamically to allow more elements as needed.

Parameters:
resizable - true iff this should grow the heap to allow more elements

BinaryHeap

public BinaryHeap(java.lang.Comparable[] array)
Initializes the array with the passed array Also takes the length of the array and sets it as the currentSize as well as maxSize for the heap, and makes heap out of that. The first element in the array (at location 0) shouldn't contain any data, as it is discraded. The array is assumed to be having values starting from location 1.

See Also:
BinaryHeap#currentSize, BinaryHeap#maxSize
Method Detail

clear

public void clear()

insert

public java.lang.Comparable insert(java.lang.Comparable x)

getMax

public java.lang.Comparable getMax()
                            throws java.util.NoSuchElementException
Returns the largest element in this, without modifying this. If this is empty, throws NoSuchElementException instead.

Throws:
java.util.NoSuchElementException

extractMax

public java.lang.Comparable extractMax()
                                throws java.util.NoSuchElementException
Throws:
java.util.NoSuchElementException

iterator

public java.util.Iterator iterator()

size

public int size()
Returns the number of elements in this.


capacity

public int capacity()
Returns the maximum number of elements in this without growing the heap.


isFull

public boolean isFull()
Returns true if this cannot store any more elements without growing the heap, i.e., size()==capacity().


isEmpty

public boolean isEmpty()
Returns true if this is empty, i.e., size()==0


toString

public java.lang.String toString()