java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips arrow java.lang arrow Priority Queue - Binary Heap - Implementation in Java
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4093
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Priority Queue - Binary Heap - Implementation in Java E-mail
User Rating: / 144
PoorBest 

A priority queue is an abstract data type (ADT) supporting the following three operations:

  • add an element to the queue with an associated priority
  • remove the element from the queue that has the highest priority, and return it
  • (optionally) peek at the element with highest priority without removing it

The simplest way to implement a priority queue data type is to keep an associative array mapping each priority to a list of elements with that priority. If association lists or hash tables are used to implement the associative array, adding an element takes constant time but removing or peeking at the element of highest priority takes linear (O(n)) time, because we must search all keys for the largest one. If a self-balancing binary search tree is used, all three operations take O(log n) time; this is a popular solution in environments that already provide balanced trees but nothing more sophisticated. The van Emde Boas tree, another associative array data structure, can perform all three operations in O(log log n) time, but at a space cost for small queues of about O(2^(m/2)), where m is the number of bits in the priority value, which may be prohibitive.

There are a number of specialized heap data structures that either supply additional operations or outperform the above approaches. The binary heap uses O(log n) time for both operations, but allows peeking at the element of highest priority without removing it in constant time. Binomial heaps add several more operations, but require O(log n) time for peeking. Fibonacci heaps can insert elements, peek at the maximum priority element, and decrease an element's priority in amortized constant time (deletions are still O(log n)).

The following code shows how to implement a priority queue in Java:

// BinaryHeap class
//
// CONSTRUCTION: empty or with initial array.
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// Comparable deleteMin( )--> Return and remove smallest item
// Comparable findMin( )  --> Return smallest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Throws UnderflowException for findMin and deleteMin when empty

/**
 * Implements a binary heap.
 * Note that all "matching" is based on the compareTo method.
 @author Mark Allen Weiss
 */
public class BinaryHeap implements PriorityQueue {
    /**
     * Construct the binary heap.
     */
    public BinaryHeap( ) {
        currentSize = 0;
        array = new ComparableDEFAULT_CAPACITY + ];
    }
    
    /**
     * Construct the binary heap from an array.
     @param items the inital items in the binary heap.
     */
    public BinaryHeapComparable [ ] items ) {
        currentSize = items.length;
        array = new Comparableitems.length + ];
        
        forint i = 0; i < items.length; i++ )
            arrayi + = items];
        buildHeap( );
    }
    
    /**
     * Insert into the priority queue.
     * Duplicates are allowed.
     @param x the item to insert.
     @return null, signifying that decreaseKey cannot be used.
     */
    public PriorityQueue.Position insertComparable x ) {
        ifcurrentSize + == array.length )
            doubleArray( );
        
        // Percolate up
        int hole = ++currentSize;
        array= x;
        
        for; x.compareToarrayhole / ] ) 0; hole /= )
            arrayhole = arrayhole / ];
        arrayhole = x;
        
        return null;
    }
    
    /**
     @throws UnsupportedOperationException because no Positions are returned
     * by the insert method for BinaryHeap.
     */
    public void decreaseKeyPriorityQueue.Position p, Comparable newVal ) {
        throw new UnsupportedOperationException"Cannot use decreaseKey for binary heap" );
    }
    
    /**
     * Find the smallest item in the priority queue.
     @return the smallest item.
     @throws UnderflowException if empty.
     */
    public Comparable findMin( ) {
        ifisEmpty( ) )
            throw new UnderflowException"Empty binary heap" );
        return array];
    }
    
    /**
     * Remove the smallest item from the priority queue.
     @return the smallest item.
     @throws UnderflowException if empty.
     */
    public Comparable deleteMin( ) {
        Comparable minItem = findMin( );
        array= arraycurrentSize-- ];
        percolateDown);
        
        return minItem;
    }
    
    /**
     * Establish heap order property from an arbitrary
     * arrangement of items. Runs in linear time.
     */
    private void buildHeap( ) {
        forint i = currentSize / 2; i > 0; i-- )
            percolateDown);
    }
    
    /**
     * Test if the priority queue is logically empty.
     @return true if empty, false otherwise.
     */
    public boolean isEmpty( ) {
        return currentSize == 0;
    }
    
    /**
     * Returns size.
     @return current size.
     */
    public int size( ) {
        return currentSize;
    }
    
    /**
     * Make the priority queue logically empty.
     */
    public void makeEmpty( ) {
        currentSize = 0;
    }
    
    private static final int DEFAULT_CAPACITY = 100;
    
    private int currentSize;      // Number of elements in heap
    private Comparable [ ] array; // The heap array
    
    /**
     * Internal method to percolate down in the heap.
     @param hole the index at which the percolate begins.
     */
    private void percolateDownint hole ) {
        int child;
        Comparable tmp = arrayhole ];
        
        for; hole * <= currentSize; hole = child ) {
            child = hole * 2;
            ifchild != currentSize &&
                    arraychild + ].compareToarraychild ] ) )
                child++;
            ifarraychild ].compareTotmp )
                arrayhole = arraychild ];
            else
                break;
        }
        arrayhole = tmp;
    }
    
    /**
     * Internal method to extend array.
     */
    private void doubleArray( ) {
        Comparable [ ] newArray;
        
        newArray = new Comparablearray.length * ];
        forint i = 0; i < array.length; i++ )
            newArray= array];
        array = newArray;
    }
    
    // Test program
    public static void mainString [ ] args ) {
        int numItems = 10000;
        BinaryHeap h1 = new BinaryHeap( );
        Integer [ ] items = new IntegernumItems - ];
        
        int i = 37;
        int j;
        
        fori = 37, j = 0; i != 0; i = i + 37 % numItems, j++ ) {
            h1.insertnew Integer) );
            itemsnew Integer);
        }
        
        fori = 1; i < numItems; i++ )
            if( ((Integer)( h1.deleteMin( ) )).intValue( ) != i )
                System.out.println"Oops! " + i );
        
        BinaryHeap h2 = new BinaryHeapitems );
        fori = 1; i < numItems; i++ )
            if( ((Integer)( h2.deleteMin( ) )).intValue( ) != i )
                System.out.println"Oops! " + i );
    }
}

// PriorityQueue interface
//
// ******************PUBLIC OPERATIONS*********************
// Position insert( x )   --> Insert x
// Comparable deleteMin( )--> Return and remove smallest item
// Comparable findMin( )  --> Return smallest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// int size( )            --> Return size
// void decreaseKey( p, v)--> Decrease value in p to v
// ******************ERRORS********************************
// Throws UnderflowException for findMin and deleteMin when empty

/**
 * PriorityQueue interface.
 * Some priority queues may support a decreaseKey operation,
 * but this is considered an advanced operation. If so,
 * a Position is returned by insert.
 * Note that all "matching" is based on the compareTo method.
 @author Mark Allen Weiss
 */
public interface PriorityQueue {
    /**
     * The Position interface represents a type that can
     * be used for the decreaseKey operation.
     */
    public interface Position {
        /**
         * Returns the value stored at this position.
         @return the value stored at this position.
         */
        Comparable getValue( );
    }
    
    /**
     * Insert into the priority queue, maintaining heap order.
     * Duplicates are allowed.
     @param x the item to insert.
     @return may return a Position useful for decreaseKey.
     */
    Position insertComparable x );
    
    /**
     * Find the smallest item in the priority queue.
     @return the smallest item.
     @throws UnderflowException if empty.
     */
    Comparable findMin( );
    
    /**
     * Remove the smallest item from the priority queue.
     @return the smallest item.
     @throws UnderflowException if empty.
     */
    Comparable deleteMin( );
    
    /**
     * Test if the priority queue is logically empty.
     @return true if empty, false otherwise.
     */
    boolean isEmpty( );
    
    /**
     * Make the priority queue logically empty.
     */
    void makeEmpty( );
    
    /**
     * Returns the size.
     @return current size.
     */
    int size( );
    
    /**
     * Change the value of the item stored in the pairing heap.
     * This is considered an advanced operation and might not
     * be supported by all priority queues. A priority queue
     * will signal its intention to not support decreaseKey by
     * having insert return null consistently.
     @param p any non-null Position returned by insert.
     @param newVal the new value, which must be smaller
     *    than the currently stored value.
     @throws IllegalArgumentException if p invalid.
     @throws UnsupportedOperationException if appropriate.
     */
    void decreaseKeyPosition p, Comparable newVal );
}


/**
 * Exception class for access in empty containers
 * such as stacks, queues, and priority queues.
 @author Mark Allen Weiss
 */
public class UnderflowException extends RuntimeException {
    /**
     * Construct this exception object.
     @param message the error message.
     */
    public UnderflowExceptionString message ) {
        supermessage );
    }
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.