****The question is to implement two method the update and getIndex. Please the question before answering and do not copy answers online they are not correct*** here is a heap class. only methods needing implementation are getIndex and update( increase or decrease a key).  use hasmap to update a key. import java.util.Iterator; import java.util.Map.Entry; import java.util.Comparator; import java.util.NoSuchElementException; import java.util.HashMap; /** * PriorityQueue class implemented via the binary heap. */ public class WeissPriorityQueue extends WeissAbstractCollection { private HashMap indexMap;  public int getIndex(AnyType x) { //average case O(1) //returns the index of the item in the heap, (use map(indexMap) to map heap items) //or -1 if it isn't in the heap //return -1;          } //you implement this public boolean update(AnyType x) { //O(lg n) average case //or O(lg n) worst case if getIndex() is guarenteed O(1) We want a similar update() operation which increases (or decreases) the priority of the item. The item (or an equal item) will be provided and it should update the priority queue appropriately. The only way to do this efficiently is to use a map to map heap items to indexes so that you know where to start the update (in average case O(1) time). Without this, update() would be O(n) and not O(lg n). Therefore before you implement updating, you need to integrate a map into the Weiss code. Whenever an item is placed, moved, or removed from the heap, the map should updated to reflect the item's new index (or remove it from the map in the case of removal from the heap). return false; //dummy return, make sure to replace this! } /** * Construct an empty PriorityQueue. */ @SuppressWarnings("unchecked") public WeissPriorityQueue( ) { currentSize = 0; cmp = null; array = (AnyType[]) new Object[ DEFAULT_CAPACITY + 1 ]; } /** * Construct an empty PriorityQueue with a specified comparator. */ @SuppressWarnings("unchecked") public WeissPriorityQueue( Comparator c ) { currentSize = 0; cmp = c; array = (AnyType[]) new Object[ DEFAULT_CAPACITY + 1 ]; } /** * Construct a PriorityQueue from another Collection. */ @SuppressWarnings("unchecked") public WeissPriorityQueue( WeissCollection coll ) { cmp = null; currentSize = coll.size( ); array = (AnyType[]) new Object[ ( currentSize + 2 ) * 11 / 10 ]; int i = 1; for( AnyType item : coll ) array[ i++ ] = item; buildHeap( ); } /** * Compares lhs and rhs using comparator if * provided by cmp, or the default comparator. */ @SuppressWarnings("unchecked") private int compare( AnyType lhs, AnyType rhs ) { if( cmp == null ) return ((Comparable)lhs).compareTo( rhs ); else return cmp.compare( lhs, rhs ); } /** * Adds an item to this PriorityQueue. * @param x any object. * @return true. */ public boolean add( AnyType x ) { if( currentSize + 1 == array.length ) doubleArray( ); // Percolate up int hole = ++currentSize; array[ 0 ] = x; for( ; compare( x, array[ hole / 2 ] ) < 0; hole /= 2 ) { array[ hole ] = array[ hole / 2 ]; } array[ hole ] = x; return true; } /** * Returns the number of items in this PriorityQueue. * @return the number of items in this PriorityQueue. */ public int size( ) { return currentSize; } /** * Make this PriorityQueue empty. */ public void clear( ) { currentSize = 0; } /**  iterator over the elements in this PriorityQueue. * The iterator does not view the elements in any particular order. */ public Iterator iterator( ) { return new Iterator( ) { int current = 0; public boolean hasNext( ) { return current != size( ); } @SuppressWarnings("unchecked") public AnyType next( ) { if( hasNext( ) ) return array[ ++current ]; else throw new NoSuchElementException( ); } public void remove( ) { throw new UnsupportedOperationException( ); } };

****The question is to implement two method the update and getIndex. Please the question before answering and do not copy answers online they are not correct***

here is a heap class. only methods needing implementation are getIndex and update( increase or decrease a key).  use hasmap to update a key.

import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Comparator;
import java.util.NoSuchElementException;

import java.util.HashMap;

/**
* PriorityQueue class implemented via the binary heap.

*/
public class WeissPriorityQueue<AnyType> extends WeissAbstractCollection<AnyType>
{

private HashMap<AnyType, Integer> indexMap; 

public int getIndex(AnyType x) {
//average case O(1)

//returns the index of the item in the heap, (use map(indexMap) to map heap items)
//or -1 if it isn't in the heap

//return -1;
  
  
  
}

//you implement this
public boolean update(AnyType x) {
//O(lg n) average case
//or O(lg n) worst case if getIndex() is guarenteed O(1)

We want a similar update() operation which increases (or decreases) the priority of the item. The item (or an equal item) will be provided and it should update the priority queue appropriately.

The only way to do this efficiently is to use a map to map heap items to indexes so that you know where to start the update (in average case O(1) time). Without this, update() would be O(n) and not O(lg n). Therefore before you implement updating, you need to integrate a map into the Weiss code. Whenever an item is placed, moved, or removed from the heap, the map should updated to reflect the item's new index (or remove it from the map in the case of removal from the heap).

return false; //dummy return, make sure to replace this!

}

/**
* Construct an empty PriorityQueue.
*/
@SuppressWarnings("unchecked")
public WeissPriorityQueue( )
{
currentSize = 0;
cmp = null;
array = (AnyType[]) new Object[ DEFAULT_CAPACITY + 1 ];
}

/**
* Construct an empty PriorityQueue with a specified comparator.
*/
@SuppressWarnings("unchecked")
public WeissPriorityQueue( Comparator<? super AnyType> c )
{
currentSize = 0;
cmp = c;
array = (AnyType[]) new Object[ DEFAULT_CAPACITY + 1 ];
}

/**
* Construct a PriorityQueue from another Collection.
*/
@SuppressWarnings("unchecked")
public WeissPriorityQueue( WeissCollection<? extends AnyType> coll )
{
cmp = null;
currentSize = coll.size( );
array = (AnyType[]) new Object[ ( currentSize + 2 ) * 11 / 10 ];

int i = 1;
for( AnyType item : coll )
array[ i++ ] = item;
buildHeap( );
}

/**
* Compares lhs and rhs using comparator if
* provided by cmp, or the default comparator.
*/
@SuppressWarnings("unchecked")
private int compare( AnyType lhs, AnyType rhs )
{
if( cmp == null )
return ((Comparable)lhs).compareTo( rhs );
else
return cmp.compare( lhs, rhs );
}

/**
* Adds an item to this PriorityQueue.
* @param x any object.
* @return true.
*/
public boolean add( AnyType x )
{
if( currentSize + 1 == array.length )
doubleArray( );

// Percolate up
int hole = ++currentSize;
array[ 0 ] = x;

for( ; compare( x, array[ hole / 2 ] ) < 0; hole /= 2 ) {
array[ hole ] = array[ hole / 2 ];
}

array[ hole ] = x;

return true;
}

/**
* Returns the number of items in this PriorityQueue.
* @return the number of items in this PriorityQueue.
*/
public int size( )
{
return currentSize;
}

/**
* Make this PriorityQueue empty.
*/
public void clear( )
{
currentSize = 0;
}

/**
 iterator over the elements in this PriorityQueue.
* The iterator does not view the elements in any particular order.
*/
public Iterator<AnyType> iterator( )
{
return new Iterator<AnyType>( )
{
int current = 0;

public boolean hasNext( )
{
return current != size( );
}

@SuppressWarnings("unchecked")
public AnyType next( )
{
if( hasNext( ) )
return array[ ++current ];
else
throw new NoSuchElementException( );
}

public void remove( )
{
throw new UnsupportedOperationException( );
}
};
}

/**
* Returns the smallest item in the priority queue.
*/
public AnyType element( )
{
if( isEmpty( ) )
throw new NoSuchElementException( );
return array[ 1 ];
}

/**
* Removes the smallest item in the priority queue.
*/
public AnyType remove( )
{
AnyType minItem = element( );
array[ 1 ] = array[ currentSize-- ];
percolateDown( 1 );

return minItem;
}private void buildHeap( )
{
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}

private static final int DEFAULT_CAPACITY = 100;

private int currentSize; // Number of elements in heap
private AnyType [ ] array; // The heap array
private Comparator<? super AnyType> cmp;

/**
* @param hole the index at which the percolate begins.
*/
private void percolateDown( int hole )
{
int child;
AnyType tmp = array[ hole ];

for( ; hole * 2 <= currentSize; hole = child )
{
child = hole * 2;
if( child != currentSize &&
compare( array[ child + 1 ], array[ child ] ) < 0 )
child++;
if( compare( array[ child ], tmp ) < 0 ) {
array[ hole ] = array[ child ];
}
else
break;
}
array[ hole ] = tmp;
}

/**
* Internal method to extend array.
*/
@SuppressWarnings("unchecked")
private void doubleArray( )
{
AnyType [ ] newArray;

newArray = (AnyType []) new Object[ array.length * 2 ];
for( int i = 0; i < array.length; i++ )
newArray[ i ] = array[ i ];
array = newArray;
}
}