HashIndexedHeap

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

Methods
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

- 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.

Class HashIndexedHeap<T>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

nodesArray

size

arrayIndexMap

maxHeap

priorityCompare

Constructor Detail

HashIndexedHeap

HashIndexedHeap

Method Detail

size

setUseMaxHeap

containsInstance

peek

poll

insert

refreshPriority

iterator

satisifiesHeap