asd_library.tree.heap
Class Heap

java.lang.Object
  |
  +--asd_library.tree.heap.Heap
All Implemented Interfaces:
Heap_adt

public class Heap
extends java.lang.Object
implements Heap_adt

The class Heap implements a max-heap


Field Summary
static int DEFAULTCAPACITY
           
 
Constructor Summary
Heap()
           
Heap(int dim)
           
 
Method Summary
static Heap array2heap(java.lang.Comparable[] data)
          Build the heap from the specified array.
 void deleteMax()
          Deletes the max element stored in this heap.
 void exchange(int index, int parent)
          Exchanges the value stored in the position index e parent in this heap.
 java.lang.Comparable getMax()
          Returns the max element in this heap.
 int getMaxChildIndex(int parent)
          Returns the child with the greatest value of the specified parent.
 int getSize()
          Returns the number of elements in this heap.
 void heapify(int i)
          Trickles down the node i until it reaches the position that reestablishes the heap order.
static void heapSort(java.lang.Comparable[] data)
          Sorting algorithm
 void insert(java.lang.Comparable key)
          Inserts the specified element key in this heap.
 boolean isEmpty()
          Verifies if this heap is empty
 boolean isFull()
          Verifies if this heap is full
 boolean isLeaf(int i)
          Verifies if the specified node i is a leaf.
 boolean isRoot(int i)
          Verifies if the specified node i is the root.
 java.lang.String toString()
          Returns a string representation of the heap.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

DEFAULTCAPACITY

public static final int DEFAULTCAPACITY
See Also:
Constant Field Values
Constructor Detail

Heap

public Heap()

Heap

public Heap(int dim)
Method Detail

getMax

public java.lang.Comparable getMax()
                            throws java.lang.Exception
Returns the max element in this heap.

Specified by:
getMax in interface Heap_adt
Returns:
max element in this heap.
Throws:
java.lang.Exception - if this heap is empty.

insert

public void insert(java.lang.Comparable key)
            throws java.lang.Exception
Inserts the specified element key in this heap.

Specified by:
insert in interface Heap_adt
Parameters:
key - element to insert.
Throws:
java.lang.Exception - if this heap is full.

deleteMax

public void deleteMax()
               throws java.lang.Exception
Deletes the max element stored in this heap.

Specified by:
deleteMax in interface Heap_adt
Throws:
java.lang.Exception - if this heap is empty.

exchange

public void exchange(int index,
                     int parent)
Exchanges the value stored in the position index e parent in this heap.

Parameters:
index - position of an element in this heap.
parent - position of an element in this heap.

getMaxChildIndex

public int getMaxChildIndex(int parent)
Returns the child with the greatest value of the specified parent.

Parameters:
parent - position of a node
Returns:
the child with the greatest value.

heapify

public void heapify(int i)
Trickles down the node i until it reaches the position that reestablishes the heap order.

Parameters:
i - node to trickle down.

isLeaf

public boolean isLeaf(int i)
Verifies if the specified node i is a leaf.

Parameters:
i - a node.
Returns:
true if i is a leaf, false otherwise.

isRoot

public boolean isRoot(int i)
Verifies if the specified node i is the root.

Parameters:
i - a node.
Returns:
true if i is the root, false otherwise.

isEmpty

public boolean isEmpty()
Verifies if this heap is empty

Returns:
true if this heap is empty, false otherwise.

isFull

public boolean isFull()
Verifies if this heap is full

Returns:
true if this heap is full, false otherwise.

getSize

public int getSize()
Returns the number of elements in this heap.

Returns:
the number of elements in this heap.

heapSort

public static void heapSort(java.lang.Comparable[] data)
Sorting algorithm

Parameters:
data - array to sorting

array2heap

public static Heap array2heap(java.lang.Comparable[] data)
Build the heap from the specified array.

Parameters:
data - an array.
Returns:
the heap.

toString

public java.lang.String toString()
Returns a string representation of the heap.

Overrides:
toString in class java.lang.Object
Returns:
a String that represents the heap.