binaryheap.java

JAVA版的蚂蚁算法(Ant Colony Optimization Algorithms)

package dk.itu.nulx30.util;

/**
 * This implementation of a binary heap is inspired by "Introduction to
 * Algorithms" Second Edition by Thomas H. Cormen et. al.
 * The <code>BinaryHeap</code> is implemented by an array starting at index 1, 
 * because of the description in the above-mentioned book.<br> 
 * The <code>BinaryHeap</code> uses two arrays:
 * <UL>
 *   <LI> <code>a</code> - which is used to implement the functionality and 
 *   <LI> <code>placement</code> - which is used to lookup the correct elements 
 *        (even though they have changed position in array <code>a</code> due
 *        to an operation).
 * </UL>
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class BinaryHeap {
  /** The number of elements in this object */  
  private int size;
  /** The array which is representing the <code>BinaryHeap</code>*/
  private BinaryHeapElement[] a;
  /** This array is used as lookup for the vertices in the binary heap*/
  private int[] placement;

  /** 
   * Class constructor which takes an initial capacity of the binary heap. 
   * If this constructor is used then the methods 
   * {@link #decreaseKey(int,double) decreaseKey( int, double )} and 
   * {@link #add(BinaryHeapElement,int) add( BinaryHeapElement, int )}
   * must not be called, because this would result in a NullPointerException.
   *
   * @param initCapacity the initial capacity of the binary heap.
   *
   * @see #decreaseKey(int,double)
   * @see #add(BinaryHeapElement,int)
   */
  public BinaryHeap( int initCapacity ) {
    size = 0;
    a = new BinaryHeapElement[ initCapacity ];
  }     

  /**
   * Class constructor which takes an array of BinaryHeapElements.
   *
   * @param newArray an array of BinaryHeapElements.
   */
  public BinaryHeap( BinaryHeapElement[] newArray ) {
    size = newArray.length;
    // This array is one element longer because index 0 isn't used. 
    a = new BinaryHeapElement[ newArray.length + 1 ];
    placement = new int[ newArray.length ];

    for ( int i = 0; i < newArray.length; i++ ) {
      a[ i + 1 ] = newArray[ i ];
      placement[ i ] = i + 1;
    }

    // Build this heap using minHeapify
    for ( int i = newArray.length / 2; i > 0; i-- ) {
      minHeapify( i );
    }
  }
  
  /**
   * returns <code>true</code> if and only if this binary heap is empty, 
   * otherwise <code>false</code>.
   *
   * @return <code>true</code> if and only if this binary heap is empty, 
   * otherwise <code>false</code>.
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * Returns the number of elements in this binary heap.
   *
   * @return the size of this <code>BinaryHeap</code> (the number of elements
   * in this heap.
   */
  public int size() {
    return size;
  }
  
  /**
   * <code>checkSize</code> examines if this binary heap is full. 
   * If this is the case then the size of this binary heap is doubled.
   */  
  private void checkSize() {
    // Index 0 is not used
    if ( size == a.length - 1 ) {
      BinaryHeapElement[] tmp = new BinaryHeapElement[ a.length * 2 ];
      System.arraycopy( a, 1, tmp, 1, size );
      a = tmp;

      // Double the size of the placement array if lookup is used.
      if ( placement != null ) {
        int[] tmp2 = new int[ placement.length * 2 ];
        System.arraycopy( placement, 1, tmp2, 1, placement.length - 1 );
        placement = tmp2;
      }
    }
  }

  /**
   * <code>insertElement</code> inserts the element into this binary
   * heap without destroying the min-heap property.
   *
   * @param element the <code>BinaryHeapElement</code> to insert into this
   * binary heap.
   *
   * @return the index of the newly inserted element.
   */
  private int insertElement( BinaryHeapElement element ) {
    int hole = ++size;

    // Percolate hole up
    for ( ; parent( hole ) > 0 && element.getPriority() <
                         a[ parent( hole ) ].getPriority(); hole = parent( hole ) ) {
      a[ hole ] = a[ parent( hole ) ];
      if ( placement != null ) {
        placement[ a[ hole ].getIndex() ] =
                                    placement[ a[ parent( hole ) ].getIndex() ];
      }
    }
    a[ hole ] = element;
    
    return hole;    
  }
  
  /**
   * adds the <code>element</code> into this binary heap without destroying
   * the min-heap property. This method cannot be used together with lookup.
   *
   * @param element the <code>BinaryHeapElement</code> to insert into this 
   * binary heap.
   */
  public void add( BinaryHeapElement element ) {
    checkSize();
    insertElement( element );
  }
  
  /**
   * adds the <code>element</code> into this binary heap without destroying
   * the min-heap property and maintaining a lookup entry. This method can only
   * be called if this binary heap was constructed with the
   * {@link #BinaryHeap(BinaryHeapElement[]) constructor} which takes an array
   * as argument.
   *
   * @param element the <code>BinaryHeapElement</code> to insert into this
   * binary heap.
   * @param index The <code>index</code> must be unique otherwise decreaseKey
   * cannot function correctly. <code>index</code> is a handle into this binary
   * heap, so decreaseKey can be called on the correct element.
   *
   * @see #BinaryHeap(BinaryHeapElement[])
   */
  public void add( BinaryHeapElement element, int index ) {
    checkSize();
    
    if ( index >= placement.length ) {
      int[] tmp2 = new int[ index * 2 ];
      System.arraycopy( placement, 1, tmp2, 1, placement.length - 1 );
      placement = tmp2;
    }

    placement[ index ] = insertElement( element );
  }

  /**
   * <code>extractMin</code> extracts the element with the minimum priority.
   * Then it reconstructs this binary heap
   *
   * @return the index of the vertex with the smallest priority.
   */
  public BinaryHeapElement extractMin() {
    if ( isEmpty() ) {
      throw new RuntimeException( "Heap underflow" );
    }
    
    BinaryHeapElement min = a[ 1 ];
    a[ 1 ] = a[ size ];
    size -= 1;
    minHeapify( 1 );

    // Make this heap half size if the size of this heap is less than 1/4
    if ( size < ( a.length - 1 ) / 4 ) {
      BinaryHeapElement[] tmp = new BinaryHeapElement[ ( a.length - 1 ) / 2 ];
      System.arraycopy( a, 1, tmp, 1, size );
      a = tmp;
    }
    
    return min;
  }

  /**
   * This method is called on this <code>BinaryHeap</code> to decrease the
   * priority of the element at index <code>i</code>. This method can only be
   * called if this binary heap was constructed with the
   * {@link #BinaryHeap(BinaryHeapElement[]) constructor} which takes an array
   * as argument and the only {@link #add(BinaryHeapElement) add-method} called
   * is the one with a lookup.
   *
   * @param index the index of the element.
   * @param key the new priority of the element.
   *
   * @see #BinaryHeap(BinaryHeapElement[])
   * @see #add(BinaryHeapElement,int)
   */
  public void decreaseKey( int index, double key ) {
    // get the correct index through the lookuplist.
    int i = placement[ index ];

    if ( key > a[ i ].getPriority() ) {
      throw new RuntimeException( "New key is larger than current key" );
    }

    a[ i ].setPriority( key );
    while ( i > 1 && a[ parent( i ) ].getPriority() > a[ i ].getPriority() ) {
      // Swap the to elements ( a[ i ] and a[ parent( i ) ] )
      // This way the indexes in the placement array still points
      // to the corresponding vertex.
      BinaryHeapElement tmp = a[ i ];
      a[ i ] = a[ parent( i ) ];
      a[ parent( i ) ] = tmp;
      // Update the indexes so that the elements points at their own
      // location
      if ( placement != null ) {
        int tmpPlacement = placement[ a[ i ].getIndex() ];
        placement[ a[ i ].getIndex() ] = placement[ a[ parent( i ) ].getIndex() ];
        placement[ a[ parent( i ) ].getIndex() ] = tmpPlacement;
      }

      i = parent( i );
    }
  }

  /**
   * This method percolates down the element at index <code>i</code> if
   * it violates the min-heap property.
   *
   * @param i the index of the element to percolate down.
   */
  private void minHeapify( int i ) {
    int l = left( i );
    int r = right( i );
    int smallest;

    if ( l <= size && a[ l ].getPriority() < a[ i ].getPriority() ) {
      smallest = l;
    }
    else {
      smallest = i;
    }

    if ( r <= size && a[ r ].getPriority() < a[ smallest ].getPriority() ) {
      smallest = r;
    }

    if ( smallest != i ) {
      // Swap the elements 
      BinaryHeapElement tmp = a[ i ];

      a[ i ] = a[ smallest ];
      a[ smallest ] = tmp;
      
      if ( placement != null ) {
        int tmpPlacement = placement[ a[ i ].getIndex() ];
        placement[ a[ i ].getIndex() ] = placement[ a[ smallest ].getIndex() ];
        placement[ a[ smallest ].getIndex() ] = tmpPlacement;
      }

      // Move further down in the heap
      minHeapify( smallest );
    }
  }

  /**
   * <code>parent</code> returns the index of the parent to the
   * given node.
   *
   * @param i the index of the element.
   *
   * @return the index of the parent to <code>i</code>.
   */
  private static int parent( int i ) {
    return i / 2;
  }

  /**
   * <code>left</code> returns the index of the left child to the
   * given node.
   *
   * @param i the index of the element.
   *
   * @return the index of the left child to <code>i</code>.
   */
  private static int left( int i ) {
    return 2 * i;
  }

  /**
   * <code>right</code> returns the index of the right child to the
   * given node.
   *
   * @param i the index of the element.
   *
   * @return the index of the right child to <code>i</code>.
   */
  private static int right( int i ) {
    return 2 * i + 1;
  }
}