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
bottom-up 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
bottom-up 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