com.meapsoft
Class Heap

java.lang.Object
  java.util.AbstractCollection
      java.util.AbstractList
          java.util.Vector
              com.meapsoft.Heap

All Implemented Interfaces:

java.lang.Cloneable, java.util.Collection, java.util.List, java.util.RandomAccess, java.io.Serializable

Direct Known Subclasses:

MaxHeap, MinHeap

public abstract class Heap

extends java.util.Vector

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.

See Also:

Serialized Form

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

isHeap

protected boolean isHeap

Constructor Detail

Heap

public Heap()

Creates an empty Heap.

Heap

public Heap(java.util.Comparator c)

Use given Comparator for all comparisons between elements in this Heap. Otherwise rely on compareTo methods and Comparable Objects.

Heap

public Heap(int capacity)

Creates an empty Heap with the given capacity.

Heap

public Heap(java.util.Collection c)

Create a new Heap containing the elements of the given Collection.

Method Detail

remove

public java.lang.Object remove(int index)

Remove the Object at the given index from the Heap

remove

public boolean remove(java.lang.Object o)

Remove the Object o from the Heap and return true. Returns false if o is not in the Heap (as measured by o.equals()).

add

public boolean add(java.lang.Object o)

Add o to the Heap.

addAll

public boolean addAll(java.util.Collection c)

Add the contents of a Collection to the Heap.

rebuildHeap

public void rebuildHeap()

Ensure that every element in this heap obeys the heap property. Runs in linear time. This is meant to be called if/when the Comparator associated with this object is modified.

sort

public void sort()

Perform an in place heap sort on the data stored in this heap. After calling sort, a call to this objects iterator() method will iterate through the data stored in the heap in ascending sorted order. This is not a stable sort.

cmp

protected int cmp(int node1,
                  int node2)

Compare two Objects in this heap - wrapper around compareTo/Comparator.compare.

isHeap

public boolean isHeap()

Do the contents of this object currently obey the heap property?