common
Class BinaryHeap

java.lang.Object
  java.util.AbstractCollection
      common.BinaryHeap

All Implemented Interfaces:

Heap, java.lang.Iterable, java.util.Collection

public class BinaryHeap
extends java.util.AbstractCollection
implements Heap

A binary heap data structure, as described in Cormen, Leiserson & Rivest (1990) Chapter 7.

Implementation note: indices in the heap are 1-based.

Nested Class Summary

Nested classes/interfaces inherited from interface common.Heap

Heap.Entry

Constructor Summary

BinaryHeap()
Creates a new, empty BinaryHeap.

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	clear() Removes all elements from this heap.
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.
boolean	isEmpty() Returns true if this heap has no entries.
java.util.Iterator	iterator() Returns an iterator over the Heap.Entry objects in this heap.
static void	main(java.lang.String[] args) Test program.
Heap.Entry	peekMin() Returns the minimum-cost entry in this heap, without modifying the heap.
int	size() Returns the number of entries in this heap.

Methods inherited from class java.util.AbstractCollection

add, addAll, contains, containsAll, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

add, addAll, contains, containsAll, equals, hashCode, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

BinaryHeap

public BinaryHeap()

Creates a new, empty BinaryHeap.

Method Detail

size

public int size()

Returns the number of entries in this heap.

Specified by:

size in interface java.util.Collection

Specified by:

size in class java.util.AbstractCollection

isEmpty

public boolean isEmpty()

Returns true if this heap has no entries.

Specified by:

isEmpty in interface java.util.Collection

Overrides:

isEmpty in class java.util.AbstractCollection

iterator

public java.util.Iterator iterator()

Returns an iterator over the Heap.Entry objects in this heap. The iteration is not guaranteed to be in any particular order. The iterator does not support removal.

Specified by:

iterator in interface java.lang.Iterable

Specified by:

iterator in interface java.util.Collection

Specified by:

iterator in class java.util.AbstractCollection

peekMin

public Heap.Entry peekMin()

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

Specified by:

peekMin in interface Heap

Throws:

java.util.NoSuchElementException - if the heap is empty

extractMin

public Heap.Entry extractMin()

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

Specified by:

extractMin in interface Heap

Throws:

java.util.NoSuchElementException - if the heap is empty

add

public 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.

Specified by:

add in interface Heap

clear

public void clear()

Removes all elements from this heap.

Specified by:

clear in interface java.util.Collection

Overrides:

clear in class java.util.AbstractCollection

decreaseCost

public 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.

Specified by:

decreaseCost in interface Heap

changeCost

public void changeCost(Heap.Entry entry,
                       double newCost)

Description copied from interface: Heap

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

Specified by:

changeCost in interface Heap

main

public static void main(java.lang.String[] args)

Test program.