public class Heap<NODE> extends Object implements IHeap<NODE>
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 and Description |
---|
Heap(Comparator<NODE> comp) |
Heap(Comparator<NODE> comp,
int capacity) |
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.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
equals, hashCode
public Heap(Comparator<NODE> comp, int capacity)
public Heap(Comparator<NODE> comp)
public NODE getMin()
IHeap
public boolean deleteMin()
IHeap
public boolean decreaseKey(NODE arg0)
IHeap
decreaseKey
in interface IHeap<NODE>
public boolean increaseKey(NODE arg0)
IHeap
increaseKey
in interface IHeap<NODE>
public boolean changedKey(NODE arg0)
IHeap
changedKey
in interface IHeap<NODE>
public boolean add(NODE arg0)
add
in interface Collection<NODE>
public boolean addAll(Collection arg0)
addAll
in interface Collection<NODE>
public boolean addAll(NODE[] arg0)
IHeap
public void clear()
clear
in interface Collection<NODE>
public boolean contains(Object arg0)
contains
in interface Collection<NODE>
public boolean containsAll(Collection arg0)
containsAll
in interface Collection<NODE>
public boolean containsAll(Object[] arg0)
IHeap
containsAll
in interface IHeap<NODE>
public boolean isEmpty()
isEmpty
in interface Collection<NODE>
public boolean remove(Object arg0)
remove
in interface Collection<NODE>
public boolean removeAll(Collection arg0)
removeAll
in interface Collection<NODE>
public boolean retainAll(Collection arg0)
retainAll
in interface Collection<NODE>
public int size()
size
in interface Collection<NODE>
public boolean empty()
IHeap
public Object[] toArray()
toArray
in interface Collection<NODE>
public Object[] toArray(Object[] arg0)
toArray
in interface Collection<NODE>
public Comparator<NODE> getComparator()
IHeap
getComparator
in interface IHeap<NODE>
Copyright © 2012 AMIS research group, Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic. All Rights Reserved.