increaseKey() method for Binary Heap ADT

Question

I have to implement increaseKey() method in a Binary Heap priority queue ADT, but I just can't see how to do it. The BinaryHeap just accept objects that extends Comparable which allows me to use a.compareTo(b), but there is no obvious way to increase the key of an object.

public class PrQueue <E extends Comparable<? super E>>
{
   // Parameters
   private static final int DEAFULT_CAPACITY = 10;
   private E[] theItems;
   private int theSize;

   // Constructors
   /**
   * Creates an empty priority queue
   */

   public PrQueue();
   /**
   * Creates a priority queue from an array
   * @param e Array of elements
   */
   public PrQueue(E[] e);

   /**
   * This Method orders the elements of the Array
   * from smallest to biggest
   */
   private void orderPr();
   // Methods
   /**
   * Inserts e in the priority queue
   * @param e the element to insert in the 
   * queue according to its priority value
   */
   public void insert(E e);

   private void ensureCapacity (int capacity);

   /**
   * Obtains the element with the lowest priority value
   * @return the element with he lowest priority
   */
   public E findMin();

   /**
   * Removes the element with the lowest priority value
   * @return the element with the lowest priority value 
   * prior to the deletion
   */
   public E deleteMin();

   /**
   * Removes all the elements of the queue
   */
   public void makeEmpty();

   /**
  * Tells if the queue is empty
  * @return true if this queue is empty, false otherwise
  */
   public boolean isEmpty();


  /**
  * Lowers the value of the item at position p by d amount
  * @param p position of the item
  * @param d amount
  * @return
  */
  public boolean decreaseKey(int p, int d)
  {

  }

  /**
  * 
  * @param p
  * @param d
  * @return
  */
 public boolean increaseKey(int p, int d)
 {

 }


 /**
 * Removes the element at pth position
 * @param p position
 * @return deleted element
 */
 public E delete(int p);


}

So, any ideas of how to do this? I've searched on google and here, but in the binaryheap implementations I've seen so far, they do not include these methods, or they return an error.

Answer 1

Change the priority value of the element, then call orderPr to ensure that it is in the right place in the data structure, and if it isn't, it is moved there.

But how do you change the priority value of the element, since E provides no methods to do so? Well... the obvious solution is to add a new method to E, which you can do by making it extend a new interface (with a new method setPriority), which extends Comparable.

There are other possible solutions, but they are not so elegant.