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

Package class diagram package Heap
java.lang.Object
  extended by 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
Heap(Comparator<NODE> comp)
           
Heap(Comparator<NODE> comp, int capacity)
           
 
Method Summary
 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:


Copyright © 2012 AMIS research group, Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic. All Rights Reserved.