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

Class mjr.heap.HeapDescending

java.lang.Object
   |
   +----java.util.Vector
           |
           +----mjr.heap.HeapDescending

public class HeapDescending
extends Vector
implements HeapImpl
An implementation of a priority queue according to Cormen, Leiserson and Rivest. Sorts in descending order.

Constructor Index

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

Method Index

 o exchange(int, int)
Exchanges the elements stored at the two locations
 o extractMax()
Removes the maximum (top) element from the Heap, decreases the size of the heap by one, and returns the maximum 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 HeapDescending
  public HeapDescending(Heapable anArray[])
Constructs the heap in O(N) time, using a technique similar to bottom-up construction.
 o HeapDescending
  public HeapDescending()
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 extractMax
  public synchronized Heapable extractMax() throws NoSuchElementException
Removes the maximum (top) element from the Heap, decreases the size of the heap by one, and returns the maximum 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