/*  Heap.java	1.0 07/27/1999   Laurentiu Cristofor   Copyright (c) 1999 Laurentiu Cristofor  *//*GAClust - Clustering categorical databases using genetic algorithmsCopyright (C) 2002  Dana CristoforThis program is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2 of the License, or (atyour option) any later version.This program is distributed in the hope that it will be useful, butWITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNUGeneral Public License for more details.You should have received a copy of the GNU General Public Licensealong with this program; if not, write to the Free SoftwareFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307USAGAClust was written by Dana Cristofor (dana@cs.umb.edu).*//** * An implementation of a heap. Elements stored in the heap must * implement the Comparable interface. * * @author	Laurentiu Cristofor * @version 	1.0, July 27th, 1999 * */public class Heap{  private Comparable[] heap;  private int size;  private int capacity;  private int capacityIncrement;  /**   * Construct a heap with initial capacity 10    * and capacity increment 0   *   * @since   1.0   * */  public Heap()  {    this(10, 0);  }  /**   * Construct a heap with initial capacity c   * and capacity increment 0   *    * @param c   initial capacity for heap   * @exception IllegalArgumentException   c is negative   * @since   1.0   * */  public Heap(int c)  {    this(c, 0);  }  /**   * Construct a heap with initial capacity c   * and capacity increment ci   *    * @param c   initial capacity for heap   * @param ci  capacity increment for heap   * @exception IllegalArgumentException   c or ci is negative   * @since   1.0   * */  public Heap(int c, int ci)  {    if (c < 0 || ci < 0)      throw new IllegalArgumentException();        size              = 0;    capacity          = c;    capacityIncrement = ci;    heap = new Comparable[capacity + 1];  }  /**   * Return the size of the heap   *   * @return   the number of elements contained in the heap   * @since   1.0   * */  public int size()  {    return size;  }  /**   * Return the capacity of the heap   *   * @return   the size of the internal array used to store the heap   * @since   1.0   * */  public int capacity()  {    return capacity;  }  /**   * Insert an element into the heap   *    * @param value   object to insert   * @exception IllegalArgumentException   value is null   * @since   1.0   * */  public void insert(Comparable value)  {    if (value == null)      throw new IllegalArgumentException();    if (size == capacity)      {	if (capacityIncrement == 0)	  capacity *= 2;	else	  capacity += capacityIncrement;	Comparable[] temp = new Comparable[capacity + 1];	System.arraycopy(heap, 1, temp, 1, size);	heap = temp;      }    heap[++size] = value;     // add at end of array    siftUp(heap, size, size); // restore heap property  }  /**   * Remove top element from the heap   *    * @return   the element with the greatest value from the heap   * @exception EmptyHeapException   heap is empty   * @since   1.0   * */  public Comparable remove() throws EmptyHeapException  {    switch (size)      {      case 0:	throw new EmptyHeapException();	      case 1:	return heap[size--]; // special case for size = 1	      default:	Comparable ret = heap[1]; // will return top element	heap[1] = heap[size--];   // move last element at top and adjust size	siftDown(heap, size, 1);  // restore heap property	return ret;      }  }  /*   * Sift an element up to its correct place in the heap   *    * @param A   array containing the heap   * @param size   size of heap   * @param pos   position of element that we sift up   * @exception IllegalArgumentException   pos < 1 or pos > size    *                                       or size > A.length   * @since   1.0   * */  private static void siftUp(Comparable[] A, int size, int pos)  {    if (pos < 1 || pos > size || size > A.length)      throw new IllegalArgumentException();    int child  = pos;    int parent = child / 2;    Comparable value = A[child];    while (parent > 0)      {	if (A[parent].compareTo(value) < 0)	  {	    A[child] = A[parent];	    child = parent;	    parent = parent / 2;	  }	else	  break;      }    A[child] = value;  }  /*   * Sift an element down to its correct place in the heap   *    * @param A   array containing the heap   * @param size   size of heap   * @param pos   position of element that we sift down   * @exception IllegalArgumentException   pos < 1 or pos > size    *                                       or size > A.length   * @since   1.0   * */  private static void siftDown(Comparable[] A, int size, int pos)  {    if (pos < 1 || pos > size || size > A.length)      throw new IllegalArgumentException();    int parent = pos;    int child  = 2 * parent;    Comparable value = A[parent];    while (child <= size)      {	if (child < size && A[child].compareTo(A[child + 1]) < 0)	  child++;	if (A[child].compareTo(value) > 0)	  {	    A[parent] = A[child];	    parent    = child;	    child     = 2 * child;	  }	else	  break;      }    A[parent] = value;  }  /*   * Transform an array into a heap   *    * @param A   array that we want to transform into a heap   * @param size   number of elements   * @exception IllegalArgumentException   size > A.length   * @since   1.0   * */  private static void heapify(Comparable[] A, int size)  {    if (size > A.length)      throw new IllegalArgumentException();    for (int i = size / 2; i > 0; i--)      siftDown(A, size, i);  }}