org.onlab.graph

Class Heap<T>

java.lang.Object

org.onlab.graph.Heap<T>

Type Parameters:

T - type of the items on the heap

public class Heap<T>
extends java.lang.Object

Implementation of an array-backed heap structure whose sense of order is imposed by the provided comparator.

While this provides similar functionality to PriorityQueue data structure, one key difference is that external entities can control when to restore the heap property, which is done through invocation of the heapify() method.

This class is not thread-safe and care must be taken to prevent concurrent modifications.

Constructor Summary

Constructors

Constructor and Description
Heap(java.util.List<T> data, java.util.Comparator<T> comparator) Creates a new heap backed by the specified list.

Method Summary

Modifier and Type	Method and Description
boolean	equals(java.lang.Object obj)
T	extractExtreme() Extracts and returns the most extreme item from the heap.
T	extreme() Returns the most extreme item in the heap.
int	hashCode()
void	heapify() Restores the heap property by re-arranging the elements in the backing array as necessary following any heap modifications.
Heap<T>	insert(T item) Inserts the specified item into the heap and returns the modified heap.
boolean	isEmpty() Returns true if there are no items in the heap.
java.util.Iterator<T>	iterator() Returns iterator to traverse the heap level-by-level.
int	size() Returns the current size of the heap.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Heap

public Heap(java.util.List<T> data,
            java.util.Comparator<T> comparator)

Creates a new heap backed by the specified list. In the interest of efficiency, the list should be array-backed. Also, for the same reason, the data is not copied and therefore, the caller must assure that the backing data is not altered in any way.

Parameters:

data - backing data list

comparator - comparator for ordering the heap items

Method Detail

heapify

public void heapify()

Restores the heap property by re-arranging the elements in the backing array as necessary following any heap modifications.

size

public int size()

Returns the current size of the heap.

Returns:

number of items in the heap

isEmpty

public boolean isEmpty()

Returns true if there are no items in the heap.

Returns:

true if heap is empty

extreme

public T extreme()

Returns the most extreme item in the heap.

Returns:

heap extreme or null if the heap is empty

extractExtreme

public T extractExtreme()

Extracts and returns the most extreme item from the heap.

Returns:

heap extreme or null if the heap is empty

insert

public Heap<T> insert(T item)

Inserts the specified item into the heap and returns the modified heap.

Parameters:

item - item to be inserted

Returns:

the heap self

Throws:

java.lang.IllegalArgumentException - if the heap is already full

iterator

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

Returns iterator to traverse the heap level-by-level. This iterator does not permit removal of items.

Returns:

non-destructive heap iterator

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object