common
Interface Heap

All Superinterfaces:

java.util.Collection, java.lang.Iterable

All Known Implementing Classes:

BinaryHeap, FibHeap

public interface Heap
extends java.util.Collection

Collection with an extractMin for efficiently getting the minimum-cost element. Rather than just holding objects and using a comparator to compare them (like java.util.TreeSet does), implementations of this interface hold Heap.Entry objects, which consist of an object and a real-valued cost. The decreaseCost method can be used to decrease an entry's cost and update its position in the heap.

Nested Class Summary

static interface

Heap.Entry Interface for entries in a heap.

Method Summary

Heap.Entry	add(java.lang.Object o, double cost) Adds an entry to this heap for the given object and cost.
void	changeCost(Heap.Entry entry, double newCost) Changes the cost for the given entry.
void	decreaseCost(Heap.Entry entry, double newCost) Decreases the cost for the given entry.
Heap.Entry	extractMin() Returns the minimum-cost entry in this heap and removes it from the heap.
Heap.Entry	peekMin() Returns the minimum-cost entry in this heap, without modifying the heap.

Methods inherited from interface java.util.Collection

add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray

Method Detail

peekMin

Heap.Entry peekMin()

Returns the minimum-cost entry in this heap, without modifying the heap.

Throws:

java.util.NoSuchElementException - if the heap is empty

extractMin

Heap.Entry extractMin()

Returns the minimum-cost entry in this heap and removes it from the heap.

Throws:

java.util.NoSuchElementException - if the heap is empty

add

Heap.Entry add(java.lang.Object o,
               double cost)

Adds an entry to this heap for the given object and cost. This does not affect any other entries for the same object. Returns the entry that was added.

decreaseCost

void decreaseCost(Heap.Entry entry,
                  double newCost)

Decreases the cost for the given entry. The entry must already be in this heap, and the new cost must be less than or equal to its current cost.

Warning: If the new cost is greater than the current one, this method will not produce an error message, but the heap may behave incorrectly.

changeCost

void changeCost(Heap.Entry entry,
                double newCost)

Changes the cost for the given entry. The entry must already be in this heap.