com.hp.ds.heap

Class Heap<T>

java.lang.Object

com.hp.ds.heap.Heap<T>

Type Parameters:

T - type of item on the heap

public class Heap<T>
extends Object

Simple array-backed heap implementation that relies on the supplied comparator to impose the sense of order.

This class is not thread-safe.

Unlike the PriorityQueue, this class allows external entities to force re-establishment of the heap property via heapify method as a response to any mutations in elements' relative priorities.

Author:

Thomas Vachuska

Constructor Summary

Constructors

Constructor and Description
Heap(T[] data, int size, Comparator<T> comparator) Creates a new heap using the supplied array of items as the heap backing.

Method Summary

Methods

Modifier and Type	Method and Description
T	extractExtreme() Extracts the item that represents the heap extreme.
T	extreme() Returns the item that represents the heap extreme.
void	heapify() Rearranges the backing array of items to establish the heap property.
Heap<T>	insert(T item) Inserts a new item into the heap.
boolean	isEmpty() Indicates whether the heap contains any items or not.
Iterator<T>	iterator() Returns non-destructive level-by-level top-down heap iterator.
int	size() Returns the heap size, i.e.

Methods inherited from class java.lang.Object

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

Constructor Detail

Heap

public Heap(T[] data,
    int size,
    Comparator<T> comparator)

Creates a new heap using the supplied array of items as the heap backing. The size of array serves as the maximum allowed heap-size. Any insertions into the heap beyond this size will be prevented.

Parameters:

data - array to be used as heap backing

size - initial size of heap

comparator - comparator to be used for comparing items

Method Detail

heapify

public void heapify()

Rearranges the backing array of items to establish the heap property.

This should be called following any change of the item key value.

size

public int size()

Returns the heap size, i.e. number if items in the heap

Returns:

heap size

isEmpty

public boolean isEmpty()

Indicates whether the heap contains any items or not.

Returns:

true if the heap is empty

extreme

public T extreme()

Returns the item that represents the heap extreme.

Returns:

heap extreme (min/max); null if heap is empty

extractExtreme

public T extractExtreme()

Extracts the item that represents the heap extreme.

Returns:

heap extreme; null if heap is empty

insert

public Heap<T> insert(T item)

Inserts a new item into the heap.

Parameters:

item - item to be inserted

Returns:

self

Throws:

IllegalStateException - if the heap is full

iterator

public Iterator<T> iterator()

Returns non-destructive level-by-level top-down heap iterator.

Returns:

heap iterator