Class mjr.heap.HeapAscending 
All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class mjr.heap.HeapAscending 

java.lang.Object
   |
   +----java.util.Vector
           |
           +----mjr.heap.HeapAscending
public class HeapAscending
extends Vector
implements HeapImpl
An implementation of a priority queue according to Cormen, Leiserson and Rivest. Sorts in ascending order.

Constructor Index

o HeapAscending(Heapable[])
Constructs the heap in O(N) time, using a technique similar to bottom-up construction.
o HeapAscending()
Constructs a heap with no elements.

Method Index

o exchange(int, int)
Exchanges the elements stored at the two locations
o extractMin()
Removes the minimum (top) element from the Heap, decreases the size of the heap by one, and returns the minimum element.
o heapify(int)
Also known as downheap, restores the heap condition starting at node i and working its way down.
o insert(Heapable)
Inserts key into the heap, and then upheaps that key to a position where the heap property is satisfied.
o left(int)
Returns the Vector index of the left child
o parent(int)
Returns the Vector index of the parent
o preorder(int, TreeGraphics)
Performs a preorder traversal of the heap, calling tg.DrawInternal on every key and tg.DrawLeaf for every child that exceeds the length of the heap (and is therefore a "leaf")
o remove()
Removes an element from the heap.
o right(int)
Returns the Vector index of the right child

Constructors

o HeapAscending 
  public HeapAscending(Heapable anArray[])
Constructs the heap in O(N) time, using a technique similar to bottom-up construction.
o HeapAscending 
  public HeapAscending()
Constructs a heap with no elements.

Methods

o left 
  protected int left(int i)
Returns the Vector index of the left child
o right 
  protected int right(int i)
Returns the Vector index of the right child
o parent 
  protected int parent(int i)
Returns the Vector index of the parent
o exchange 
  protected synchronized void exchange(int i,
                                       int j)
Exchanges the elements stored at the two locations
o heapify 
  protected synchronized void heapify(int i)
Also known as downheap, restores the heap condition starting at node i and working its way down.
o extractMin 
  public synchronized Heapable extractMin() throws NoSuchElementException
Removes the minimum (top) element from the Heap, decreases the size of the heap by one, and returns the minimum element.
o remove 
  public Heapable remove() throws NoSuchElementException
Removes an element from the heap.
o insert 
  public synchronized void insert(Heapable key)
Inserts key into the heap, and then upheaps that key to a position where the heap property is satisfied.
o preorder 
  public void preorder(int i,
                       TreeGraphics tg)
Performs a preorder traversal of the heap, calling tg.DrawInternal on every key and tg.DrawLeaf for every child that exceeds the length of the heap (and is therefore a "leaf") 
All Packages  Class Hierarchy  This Package  Previous  Next  Index