|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object java.util.AbstractCollection java.util.AbstractList java.util.Vector com.meapsoft.Heap
Abstract implementation of the basic functions needed for a binary heap using java.util.Vector as a back end. Unlike java.util.TreeSet, this data structure can handle duplicate entries. The implementations of the methods given here implement a MinHeap. It is abstract so that we can have a MinHeap class that supports deleteMin() and a MaxHeap class that supports deleteMax() but neither of them support both.
Field Summary | |
protected boolean |
isHeap
|
Fields inherited from class java.util.Vector |
capacityIncrement, elementCount, elementData |
Fields inherited from class java.util.AbstractList |
modCount |
Constructor Summary | |
Heap()
Creates an empty Heap. |
|
Heap(java.util.Collection c)
Create a new Heap containing the elements of the given Collection. |
|
Heap(java.util.Comparator c)
Use given Comparator for all comparisons between elements in this Heap. |
|
Heap(int capacity)
Creates an empty Heap with the given capacity. |
Method Summary | |
boolean |
add(java.lang.Object o)
Add o to the Heap. |
boolean |
addAll(java.util.Collection c)
Add the contents of a Collection to the Heap. |
protected int |
cmp(int node1,
int node2)
Compare two Objects in this heap - wrapper around compareTo/Comparator.compare. |
boolean |
isHeap()
Do the contents of this object currently obey the heap property? |
void |
rebuildHeap()
Ensure that every element in this heap obeys the heap property. |
java.lang.Object |
remove(int index)
Remove the Object at the given index from the Heap |
boolean |
remove(java.lang.Object o)
Remove the Object o from the Heap and return true. |
void |
sort()
Perform an in place heap sort on the data stored in this heap. |
Methods inherited from class java.util.Vector |
add, addAll, addElement, capacity, clear, clone, contains, containsAll, copyInto, elementAt, elements, ensureCapacity, equals, firstElement, get, hashCode, indexOf, indexOf, insertElementAt, isEmpty, lastElement, lastIndexOf, lastIndexOf, removeAll, removeAllElements, removeElement, removeElementAt, removeRange, retainAll, set, setElementAt, setSize, size, subList, toArray, toArray, toString, trimToSize |
Methods inherited from class java.util.AbstractList |
iterator, listIterator, listIterator |
Methods inherited from class java.lang.Object |
finalize, getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface java.util.List |
iterator, listIterator, listIterator |
Field Detail |
protected boolean isHeap
Constructor Detail |
public Heap()
public Heap(java.util.Comparator c)
public Heap(int capacity)
public Heap(java.util.Collection c)
Method Detail |
public java.lang.Object remove(int index)
public boolean remove(java.lang.Object o)
public boolean add(java.lang.Object o)
public boolean addAll(java.util.Collection c)
public void rebuildHeap()
public void sort()
protected int cmp(int node1, int node2)
public boolean isHeap()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |