com.cogent.util
Class MinHeap

java.lang.Object
  |
  +--com.cogent.util.MinHeap

public class MinHeap
extends java.lang.Object

A Min Heap for a priority queue implementation. Taken from Data Structures and the Java Collections Framework by William J. Collins.


Field Summary
protected  java.util.Comparator comparator
           
protected  java.lang.Object[] heap
           
private static int INITIAL_CAPACITY
           
protected  int size
           
 
Constructor Summary
MinHeap()
           
MinHeap(java.util.Comparator comp)
           
 
Method Summary
 void add(java.lang.Object element)
           
private  int compare(java.lang.Object elem1, java.lang.Object elem2)
           
 java.lang.Object getMin()
           
protected  void percolateDown(int start)
           
protected  void percolateUp()
           
 java.lang.Object removeMin()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

INITIAL_CAPACITY

private static final int INITIAL_CAPACITY
See Also:
Constant Field Values

heap

protected java.lang.Object[] heap

size

protected int size

comparator

protected java.util.Comparator comparator
Constructor Detail

MinHeap

public MinHeap()

MinHeap

public MinHeap(java.util.Comparator comp)
Method Detail

add

public void add(java.lang.Object element)

percolateUp

protected void percolateUp()

compare

private int compare(java.lang.Object elem1,
                    java.lang.Object elem2)

getMin

public java.lang.Object getMin()

removeMin

public java.lang.Object removeMin()

percolateDown

protected void percolateDown(int start)