HeapPriorityQueue

Discussion in 'Java' started by gabbadd, Nov 17, 2003.

  1. gabbadd

    gabbadd Guest

    Hello Anyone who can assist in getting this code to work. Thanks.

    package priorityq;

    /**
    * Defines an implementation of a Priority Queue using a heap
    * represented with an array

    */

    public class HeapPriorityQueue implements PriorityQueue
    {
    private final int SIZE = 1000;
    private MyElement a[];
    private int size;

    /**
    * Builds an array of MyElements of default size SIZE
    */

    public HeapPriorityQueue()
    {
    // Creates array of MyElement
    this.a = new MyElement[ SIZE ];
    size = 0;
    }

    /**
    * Builds an array of MyElements of default size size
    *
    * @param size
    */

    public HeapPriorityQueue( int size )
    {
    // Creates array of MyElement
    this.a = new MyElement[ size ];
    this.size = 0;
    }

    // returns number of elements in the queue
    public int size()
    {

    }

    // returns true if the queue is empty
    public boolean isEmpty()
    {
    return (size == 0);
    }

    // insert the pair (k,o)
    public void enqueue( int key, Object obj ) throws QueueException
    {

    }

    // extract object with maximum key
    public Object maxElement() throws QueueException
    {

    }

    // extract maximum key (without removing the element from the queue)
    public int maxKey() throws QueueException
    {

    }

    // Remove element with min key
    public void remove() throws QueueException
    {

    }

    private void heapify( int i, int j )
    {
    int sx, dx, k;

    sx = 2 * i + 1;
    dx = sx + 1;

    if ( sx > j )
    return;

    if ( dx > j )
    k = sx;
    else
    k = ( a[ sx ].getKey() > a[ dx ].getKey() ) ? sx : dx;

    if ( a[ i ].getKey() < a[ k ].getKey() ) {
    swap( i, k );
    heapify( k, j );
    }
    }

    private void swap( int i, int j )
    {
    MyElement tmp;

    tmp = a[ i ];
    a[ i ] = a[ j ];
    a[ j ] = tmp;
    }

    private int father( int i )
    {
    return ( i - 1 ) / 2;
    }

    private void makeheap()
    {
    for ( int i = father( a.length - 1 ); i >= 0; i-- )
    heapify( i, a.length - 1 );
    }
    }
     
    gabbadd, Nov 17, 2003
    #1
    1. Advertising

  2. gabbadd wrote:

    > Hello Anyone who can assist in getting this code to work. Thanks.
    >

    <snip code>

    It would probably help if you say what's not working, what it does now and
    what you expect it to do.

    http://www.catb.org/~esr/faqs/smart-questions.html

    --
    Regards,
    Christophe Vanfleteren
     
    Christophe Vanfleteren, Nov 17, 2003
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page