Question
Please help,I really appreciate your assitance!! Thank you very much!!!
Using a heap, implement the priority queue ADT from Section 7.4. You can store the heap in arrays, similar to the solution to Self-Test Exercise 2. To have FIFO behavior for elements with equal priority, you should have a third array called entered. The value of entered[i] tells when the data in node number i entered the priority queue. For example, the first element added has "an entered value of 1, the second element has an entered value of 2, and so on. When you are comparing two elements with equal priority, use the entered value to "break the tie" (so that if two elements have the same priority number, then the one with the earlier entered value will come out of the priority queue first).
Make sure you keep track of how many elements are in the heap so that, if the size of the heap reaches the size of the arrays, you can increase the size of the arrays.
Explanation / Answer
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 Comparable[ DEFAULT_CAPACITY + 1 ]; } /** * Construct the binary heap from an array. * @param items the inital items in the binary heap. */ public BinaryHeap( Comparable [ ] items ) { currentSize = items.length; array = new Comparable[ items.length + 1 ]; for( int i = 0; i 0; i-- ) percolateDown( i ); } /** * 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 percolateDown( int hole ) { int child; Comparable tmp = array[ hole ]; for( ; hole * 2 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 insert( Comparable 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 decreaseKey( Position 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 UnderflowException( String message ) { super( message ); } } ***************************************************************************** also check this site its may be also useful for u...... http://eu.wiley.com/WileyCDA/WileyTitle/productCd-EHEP001656.html thx