burlap.datastructures

Class HashIndexedHeap<T>

java.lang.Object

burlap.datastructures.HashIndexedHeap<T>

Type Parameters:

T - any Java object

All Implemented Interfaces:

java.lang.Iterable<T>

public class HashIndexedHeap<T>
extends java.lang.Object
implements java.lang.Iterable<T>

An implementation of a hash map backed heap/priority queue. This data structure allows efficient O(1) "contains" checks and efficient O(lg(n)) modifications of entries already in the heap that with a typical Java PriorityQueue would require linear updates. This data structure is especially useful for planning algorithms like A* that keep a priority queue of states, but may need to update their priority if a better path to them is found.

By default, the heap is a max heap (which results in elements with the highest priority being dequeued first), but it may also be set to be a min heap.

Author:

James MacGlashan

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Map<T,java.lang.Integer>	arrayIndexMap Hash map from objects to their index in the heap
protected boolean	maxHeap If true, this is ordered according to a max heap; if false ordered according to a min heap.
protected java.util.List<T>	nodesArray Heap ordered list of objects
protected java.util.Comparator<T>	priorityCompare A comparator to compare objects
protected int	size Number of objects in the heap

Constructor Summary

Constructors

Constructor and Description
HashIndexedHeap(java.util.Comparator<T> pcompare) Initializes the heap with a comparator
HashIndexedHeap(java.util.Comparator<T> pcompare, int capacity) Initializes the heap with a comparator and an initial capacity size

Method Summary

Modifier and Type	Method and Description
T	containsInstance(T inst) Checks if the heap contains this object and returns the pointer to the stored object if it does; otherwise null is returned.
void	insert(T el) Inserts the element into the heap
java.util.Iterator<T>	iterator()
T	peek() Returns a pointer to the head of the heap without removing it
T	poll() Returns a pointer to the head of the heap and removes it
void	refreshPriority(T el) Calling this method indicates that the priority of the object passed to the method has been modified and that this heap needs to reorder its elements as a result
boolean	satisifiesHeap() This method returns whether the data structure stored is in fact a heap (costs linear time).
void	setUseMaxHeap(boolean max) Sets whether this heap is a max heap or a min heap
int	size() Returns the size of the heap

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

nodesArray

protected java.util.List<T> nodesArray

Heap ordered list of objects

size

protected int size

Number of objects in the heap

arrayIndexMap

protected java.util.Map<T,java.lang.Integer> arrayIndexMap

Hash map from objects to their index in the heap

maxHeap

protected boolean maxHeap

If true, this is ordered according to a max heap; if false ordered according to a min heap.

priorityCompare

protected java.util.Comparator<T> priorityCompare

A comparator to compare objects

Constructor Detail

HashIndexedHeap

public HashIndexedHeap(java.util.Comparator<T> pcompare)

Initializes the heap with a comparator

Parameters:

pcompare - the comparator to compare the priority of elements of this heap

HashIndexedHeap

public HashIndexedHeap(java.util.Comparator<T> pcompare,
                       int capacity)

Initializes the heap with a comparator and an initial capacity size

Parameters:

pcompare - the comparator to compare the priority of elements of this heap

capacity - the initial compacity size of the heap

Method Detail

size

public int size()

Returns the size of the heap

Returns:

the size of the heap

setUseMaxHeap

public void setUseMaxHeap(boolean max)

Sets whether this heap is a max heap or a min heap

Parameters:

max - if true, sets to be ma heap; if false sets to be min heap.

containsInstance

public T containsInstance(T inst)

Checks if the heap contains this object and returns the pointer to the stored object if it does; otherwise null is returned.

Parameters:

inst - the inst to look for in the heap

Returns:

the pointer to the stored object if it is in the heap; null otherwise.

peek

public T peek()

Returns a pointer to the head of the heap without removing it

Returns:

a pointer to the head of the heap

poll

public T poll()

Returns a pointer to the head of the heap and removes it

Returns:

a pointer to the head of the heap

insert

public void insert(T el)

Inserts the element into the heap

Parameters:

el - the element to be inserted

refreshPriority

public void refreshPriority(T el)

Calling this method indicates that the priority of the object passed to the method has been modified and that this heap needs to reorder its elements as a result

Parameters:

el - the element whose priority was modified

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T>

satisifiesHeap

public boolean satisifiesHeap()

This method returns whether the data structure stored is in fact a heap (costs linear time). This method should only be used for debug purposes such as when a heap's elements have their priority changed from multiple sources and it needs to be made sure that each element is being properly refreshed within the heap. Note that to be a heap, each node must be greater than or equal to its children.

Returns:

true if the stored data is a valid heap; false otherwise.