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.

HeapDescending(Heapable[])
 Constructs the heap in O(N) time, using a technique similar to
bottomup construction.

HeapDescending()
 Constructs a heap with no elements.

exchange(int, int)
 Exchanges the elements stored at the two locations

extractMax()
 Removes the maximum (top) element from the Heap, decreases the
size of the heap by one, and returns the maximum element.

heapify(int)
 Also known as downheap, restores the heap condition
starting at node i and working its way down.

insert(Heapable)
 Inserts key into the heap, and then upheaps that key to a
position where the heap property is satisfied.

left(int)
 Returns the Vector index of the left child

parent(int)
 Returns the Vector index of the parent

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")

remove()
 Removes an element from the heap.

right(int)
 Returns the Vector index of the right child
HeapDescending
public HeapDescending(Heapable anArray[])
 Constructs the heap in O(N) time, using a technique similar to
bottomup construction.
HeapDescending
public HeapDescending()
 Constructs a heap with no elements.
left
protected int left(int i)
 Returns the Vector index of the left child
right
protected int right(int i)
 Returns the Vector index of the right child
parent
protected int parent(int i)
 Returns the Vector index of the parent
exchange
protected synchronized void exchange(int i,
int j)
 Exchanges the elements stored at the two locations
heapify
protected synchronized void heapify(int i)
 Also known as downheap, restores the heap condition
starting at node i and working its way down.
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.
remove
public Heapable remove() throws NoSuchElementException
 Removes an element from the heap.
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.
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