infovis.utils
Class Heap

java.lang.Object
  extended by infovis.utils.Heap

public class Heap
extends Object

An array-based binary heap implementation of a priority queue, which also provides an efficient update() operation. (A previous version of this class had implemented the commons-collections PriorityQueue interface, which has since been deprecated.) It contains extra infrastructure (a hash table) to keep track of the position of each element in the array; thus, if the key value of an element changes, it may be "resubmitted" to the heap via update so that the heap can reposition it efficiently, as necessary.

Author:
Joshua O'Madadhain

Constructor Summary
Heap()
          Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
Heap(Comparator c)
          Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.
 
Method Summary
 void clear()
           
 void insert(Object o)
           
 boolean isEmpty()
           
 Object peek()
           
 Object pop()
           
 int size()
           
 void update(Object o)
          Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

Heap

public Heap(Comparator c)
Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.


Heap

public Heap()
Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.

Method Detail

clear

public void clear()

insert

public void insert(Object o)

isEmpty

public boolean isEmpty()

peek

public Object peek()
            throws NoSuchElementException
Throws:
NoSuchElementException

pop

public Object pop()
           throws NoSuchElementException
Throws:
NoSuchElementException

size

public int size()

update

public void update(Object o)
Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).

Parameters:
o -


Copyright 2005 by Jean-Daniel Fekete and INRIA, France All rights reserved.