All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class DataStructures.BinaryHeap 

java.lang.Object
   |
   +----DataStructures.BinaryHeap
public class BinaryHeap
extends Object
implements PriorityQueue
Implements a binary heap. Allows lazy insertion and provides a linear-time heap construction method. Note that all "matching" is based on the compares method.

Constructor Index

o BinaryHeap(Comparable)
Construct the binary heap.

Method Index

o deleteMin()
Remove the smallest item from the priority queue.
o findMin()
Find the smallest item in the priority queue.
o fixHeap()
Re-establish heap order property after a series of toss operations.
o insert(Comparable)
Insert into the priority queue, maintaining heap order.
o isEmpty()
Test if the priority queue is logically empty.
o main(String[])
o makeEmpty()
Make the priority queue logically empty.
o toss(Comparable)
Insert into the priority queue, without maintaining heap order.

Constructors

o BinaryHeap 
  public BinaryHeap(Comparable negInf)
Construct the binary heap.

Parameters:
negInf - a value smaller than or equal to all others.

Methods

o insert 
  public void insert(Comparable x)
Insert into the priority queue, maintaining heap order. Duplicates are allowed.

Parameters:
x - the item to insert.
o toss 
  public void toss(Comparable x)
Insert into the priority queue, without maintaining heap order. Duplicates are allowed.

Parameters:
x - the item to insert.
o findMin 
  public Comparable findMin() throws Underflow
Find the smallest item in the priority queue.

Returns:
the smallest item.
Throws: Underflow
if the priority queue is empty.
o deleteMin 
  public Comparable deleteMin() throws Underflow
Remove the smallest item from the priority queue.

Throws: Underflow
if the priority queue is empty.
o fixHeap 
  public void fixHeap()
Re-establish heap order property after a series of toss operations. Runs in linear time.

o isEmpty 
  public boolean isEmpty()
Test if the priority queue is logically empty.

Returns:
true if empty, false otherwise.
o makeEmpty 
  public void makeEmpty()
Make the priority queue logically empty.

o main 
  public static void main(String args[])

All Packages  Class Hierarchy  This Package  Previous  Next  Index