heaps.generic
Class FastGenericHeap<E>

java.lang.Object
  heaps.generic.GenericHeap<E>
      heaps.generic.FastGenericHeap<E>

Type Parameters:

E - the type of all heap objects

All Implemented Interfaces:

Heap<E>

public class FastGenericHeap<E>
extends GenericHeap<E>

A fast implementation of the GenericHeap interface that does not allow duplicates. For an array of N elements, this class executes the methods of GenericHeap that depend on the implementation in O(lg N) time. These methods are faster than their counterparts implemented in SingletonGenericHeap because heap elements are mapped to their position in the backing array using a HashMap. All other operations defined in Heap run in constant, or O(1), time.

Author:

Michael Parker

Constructor Summary

FastGenericHeap()
Creates a new heap with the backing array having an initial size of 16.

FastGenericHeap(java.util.Comparator<? super E> _comp)
Creates a new heap with the backing array having an initial size of 16.

FastGenericHeap(java.util.Comparator<? super E> _comp, int _init_capacity)
Creates a new heap with the backing array having the specified initial size.

FastGenericHeap(int _init_capacity)
Creates a new heap with the backing array having the specified initial size.

Method Summary

boolean	add(E element) Adds the object element to the heap.
boolean	allowsDuplicates() Returns whether this heap allows duplicate elements.
void	clear() Removes all elements from the heap.
boolean	contains(E element) Returns whether the heap contains the argument element.
E	extract() Extracts the next element from the heap.
int	getSize() Returns the number of elements in the heap.
boolean	isEmpty() Returns true if the heap is empty, false otherwise.
boolean	remove(E element) Finds the object in the heap equal to element, removes it, and returns true.
E	top() Returns the next object element to be extracted from the heap without actually removing it from the heap.

Methods inherited from class heaps.generic.GenericHeap

getComparator

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FastGenericHeap

public FastGenericHeap()

Creates a new heap with the backing array having an initial size of 16. Elements are sorted by their natural ordering, so all heap elements must implement the Comparable interface and be mutually comparable.

FastGenericHeap

public FastGenericHeap(int _init_capacity)

Creates a new heap with the backing array having the specified initial size. The constructed heap relies on the natural ordering of the elements, so all heap elements must implement the Comparable interface and be mutually comparable.

Parameters:

_init_capacity - the initial size of the backing array

FastGenericHeap

public FastGenericHeap(java.util.Comparator<? super E> _comp)

Creates a new heap with the backing array having an initial size of 16. Elements are sorted by the provided comparator, and must be mutually comparable under it.

Parameters:

_comp - the comparator used to order heap elements

FastGenericHeap

public FastGenericHeap(java.util.Comparator<? super E> _comp,
                       int _init_capacity)

Creates a new heap with the backing array having the specified initial size. Elements are sorted by the provided comparator, and must be mutually comparable under it.

Parameters:

_comp - the comparator used to order heap elements

_init_capacity - the initial size of the backing array

Method Detail

clear

public void clear()

Description copied from interface: Heap

Removes all elements from the heap.

add

public boolean add(E element)

Description copied from class: GenericHeap

Adds the object element to the heap. If the implementing heap allows duplicates, element is always added to the heap and this method returns true. If the implementing heap does not allow duplicates, element is added and method returns true only if no duplicate of element exists in the heap. Otherwise, if a duplicate exists in the heap and none are allowed, this method returns false and the heap remains unchanged.

Specified by:

add in class GenericHeap<E>

Parameters:

element - the object to add to the heap

Returns:

true if element is added, false otherwise

top

public E top()

Description copied from interface: Heap

Returns the next object element to be extracted from the heap without actually removing it from the heap. If the heap is non-empty, this value returned must be the smallest of all objects in the heap, as determined by the natural ordering of Comparable. If the heap is empty, null is returned.

Returns:

the top element in the heap

extract

public E extract()

Description copied from interface: Heap

Extracts the next element from the heap. If the heap is non-empty, the value returned must be the smallest of all objects in the heap, as determined by the natural ordering of Comparable. If the heap is empty, null is returned.

Returns:

the top element removed from the heap

getSize

public int getSize()

Description copied from interface: Heap

Returns the number of elements in the heap.

Returns:

the number of heap elements

isEmpty

public boolean isEmpty()

Description copied from interface: Heap

Returns true if the heap is empty, false otherwise. This is equivalent to returning true if and only if getSize returns 0.

Returns:

true if the heap is empty, false otherwise

remove

public boolean remove(E element)

Description copied from class: GenericHeap

Finds the object in the heap equal to element, removes it, and returns true. If no such object exists, this method returns false and the heap remains unchanged. Note that if duplicates are allowed in the heap, any one of the duplicates of element could be removed.

Specified by:

remove in class GenericHeap<E>

Parameters:

element - the element to remove from the heap

Returns:

true if element is removed, false otherwise

allowsDuplicates

public boolean allowsDuplicates()

Description copied from class: GenericHeap

Returns whether this heap allows duplicate elements.

Specified by:

allowsDuplicates in class GenericHeap<E>

Returns:

true if this heap permits duplicates, false otherwise

contains

public boolean contains(E element)

Description copied from class: GenericHeap

Returns whether the heap contains the argument element.

Specified by:

contains in class GenericHeap<E>

Parameters:

element - the element to query for membership in the heap

Returns:

true if element is in the heap, false otherwise