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.

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

HeapAscending()
 Constructs a heap with no elements.

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

extractMin()
 Removes the minimum (top) element from the Heap, decreases the
size of the heap by one, and returns the minimum 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
HeapAscending
public HeapAscending(Heapable anArray[])
 Constructs the heap in O(N) time, using a technique similar to
bottomup construction.
HeapAscending
public HeapAscending()
 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.
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.
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