asd_library.tree.heap
Class Heap

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

public class Heap
extends java.lang.Object
implements PriorityQueue_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.
 java.lang.Comparable deleteFirst()
          Deletes the first 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 getFirst()
          Returns the first 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
 java.lang.Comparable 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

getFirst

public java.lang.Comparable getFirst()
Returns the first element in this heap.

Specified by:
getFirst in interface PriorityQueue_adt
Returns:
the first element in this heap.

insert

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

Specified by:
insert in interface PriorityQueue_adt
Parameters:
key - element to insert.
Returns:
the inserted elementor null if this heap is full.

deleteFirst

public java.lang.Comparable deleteFirst()
Deletes the first element stored in this heap.

Specified by:
deleteFirst in interface PriorityQueue_adt

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.