cz.cuni.amis.utils.heap

Class Heap<NODE>

java.lang.Object

cz.cuni.amis.utils.heap.Heap<NODE>

All Implemented Interfaces:

IHeap<NODE>, Iterable<NODE>, Collection<NODE>

public class Heap<NODE>
extends Object
implements IHeap<NODE>

Heap implementation as a Collection that provides "decreaseKey" operation. In order to do that, we're using a HashMap that holds references where the node lies within the heap, thus we're requiring that stored NODEs have Object.equals(Object) and Object.hashCode() implemented correctly.

Constructor Summary

Constructors

Constructor and Description
Heap(Comparator<NODE> comp)
Heap(Comparator<NODE> comp, int capacity)

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(NODE arg0)
boolean	addAll(Collection arg0)
boolean	addAll(NODE[] arg0) Adds all items from 'items'.
boolean	changedKey(NODE arg0) "node" value has been changed (not sure if it was increased or decreased), bubble it through the heap.
void	clear()
boolean	contains(Object arg0)
boolean	containsAll(Collection arg0)
boolean	containsAll(Object[] arg0) Whether this heap contains all 'items'.
boolean	decreaseKey(NODE arg0) "node" value has been decreased, bubble it through the heap.
boolean	deleteMin() Deletes node with min-value, returns success (true if there was some object in the heap, false if there weren't).
boolean	empty() Whether this heap is empty.
Comparator<NODE>	getComparator() Returns comparator that is used to compare the nodes in the heap.
NODE	getMin() Returns node with min-value from the heap.
boolean	increaseKey(NODE arg0) "node" value has been increased, bubble it through the heap.
boolean	isEmpty()
Iterator<NODE>	iterator()
boolean	remove(Object arg0)
boolean	removeAll(Collection arg0)
boolean	retainAll(Collection arg0)
int	size()
Object[]	toArray()
Object[]	toArray(Object[] arg0)
Set	toSet() Returns this heap as a set.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

equals, hashCode

Constructor Detail

Heap

public Heap(Comparator<NODE> comp,
    int capacity)

Heap

public Heap(Comparator<NODE> comp)

Method Detail

getMin

public NODE getMin()

Description copied from interface: IHeap

Returns node with min-value from the heap.

Specified by:

getMin in interface IHeap<NODE>

Returns:

deleteMin

public boolean deleteMin()

Description copied from interface: IHeap

Deletes node with min-value, returns success (true if there was some object in the heap, false if there weren't).

Specified by:

deleteMin in interface IHeap<NODE>

Returns:

success

decreaseKey

public boolean decreaseKey(NODE arg0)

Description copied from interface: IHeap

"node" value has been decreased, bubble it through the heap.

Specified by:

decreaseKey in interface IHeap<NODE>

Returns:

increaseKey

public boolean increaseKey(NODE arg0)

Description copied from interface: IHeap

"node" value has been increased, bubble it through the heap.

Specified by:

increaseKey in interface IHeap<NODE>

Returns:

changedKey

public boolean changedKey(NODE arg0)

Description copied from interface: IHeap

"node" value has been changed (not sure if it was increased or decreased), bubble it through the heap.

Specified by:

changedKey in interface IHeap<NODE>

Returns:

add

public boolean add(NODE arg0)

Specified by:

add in interface Collection<NODE>

addAll

public boolean addAll(Collection arg0)

Specified by:

addAll in interface Collection<NODE>

addAll

public boolean addAll(NODE[] arg0)

Description copied from interface: IHeap

Adds all items from 'items'.

Specified by:

addAll in interface IHeap<NODE>

Returns:

clear

public void clear()

Specified by:

clear in interface Collection<NODE>

contains

public boolean contains(Object arg0)

Specified by:

contains in interface Collection<NODE>

containsAll

public boolean containsAll(Collection arg0)

Specified by:

containsAll in interface Collection<NODE>

containsAll

public boolean containsAll(Object[] arg0)

Description copied from interface: IHeap

Whether this heap contains all 'items'.

Specified by:

containsAll in interface IHeap<NODE>

Returns:

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Collection<NODE>

iterator

public Iterator<NODE> iterator()

Specified by:

iterator in interface Iterable<NODE>

Specified by:

iterator in interface Collection<NODE>

remove

public boolean remove(Object arg0)

Specified by:

remove in interface Collection<NODE>

removeAll

public boolean removeAll(Collection arg0)

Specified by:

removeAll in interface Collection<NODE>

retainAll

public boolean retainAll(Collection arg0)

Specified by:

retainAll in interface Collection<NODE>

size

public int size()

Specified by:

size in interface Collection<NODE>

empty

public boolean empty()

Description copied from interface: IHeap

Whether this heap is empty.

Specified by:

empty in interface IHeap<NODE>

Returns:

toArray

public Object[] toArray()

Specified by:

toArray in interface Collection<NODE>

toArray

public Object[] toArray(Object[] arg0)

Specified by:

toArray in interface Collection<NODE>

toSet

public Set toSet()

Description copied from interface: IHeap

Returns this heap as a set.

Specified by:

toSet in interface IHeap<NODE>

Returns:

getComparator

public Comparator<NODE> getComparator()

Description copied from interface: IHeap

Returns comparator that is used to compare the nodes in the heap.

Specified by:

getComparator in interface IHeap<NODE>

Returns: