// Binary heap routines - root (at subscript 1) has minimum.
// Also supports handle array for linking from another data structure.
// handle[i] gives the heap subscript for the entry with
// id number i.  (Also, handle[heap[j].id]==j . . .).

public class minHeap
{

  public static class minHeapFails extends Exception
  {
    public minHeapFails()
    {
      super();
    }

    public minHeapFails(String message)
    {
      super(message);
    }
  }

  private int maxSub;        // Maximum number of elements that heap may hold.
  private int n;             // Actual entries in the heap.
  private heapEntry[] heap;  // Element 0 is not used
  private int[] handle;      // Subscripts must be in the range 0..maxSub-1

  public int left(int x)
  // Left child of x
  {
    return 2*x;
  }

  public int right(int x)
  // Right child of x
  {
    return 2*x+1;
  }

  public int parent(int x)
  // Parent of x
  {
    return x/2;
  }

  public boolean full()
  // Is this heap full?
  {
    return n==maxSub;
  }

  public boolean empty()
  // Is this heap empty?
  {
    return n==0;
  }

  public void heapify(int j)
  {
    // The subtrees to the left and right of heap[j] must have
    // the minHeap property.  At completion of this routine, the
    // entire subtree rooted at heap[j] will have the minHeap
    // property.
    int best,r;
    heapEntry entry=heap[j];

    while (true)
    {
      // Find child with smaller priority
      best=left(j);
      if (best>n)
        break;  // Gone past the leaves

      r=right(j);
      // Does left or right child have the smaller priority?
      if (r<=n && heap[best].priority>heap[r].priority)
        best=r;
      if (entry.priority<=heap[best].priority)
        break;  // minHeap property holds in subtree

      // Move best child to parent
      heap[j]=heap[best];
      handle[heap[j].id]=j;
      // Continue rippling one level deeper.
      // Again, the left and right subtrees have the minHeap property.
      j=best;
    }
    // Drop off item from root of subtree (original j)
    heap[j]=entry;
    handle[heap[j].id]=j;
  }

  public void swapUp(int j)
  {
    // Ancestors of heap[j] have the minHeap property,
    // so fixing the heap is a matter of having heap[j]
    // climb past its ancestors with larger priorities.
    int p;
    heapEntry entry=heap[j];

    p=parent(j);
    while (p>=1 && heap[p].priority>entry.priority)
    {
      heap[j]=heap[p];
      handle[heap[j].id]=j;
      j=p;
      p=parent(j);
    }

    // Drop off item with new priority
    heap[j]=entry;
    handle[heap[j].id]=j;
  }

  public int getPriority(int id) throws minHeapFails
  {
    if (id<0 || id>=maxSub || handle[id]==(-1))
      throw new minHeapFails("id "+id+" issue for getPriority");

    return heap[handle[id]].priority;
  }

  public void changePriority(heapEntry iEntry)
  {
    // Changes priority of item iId to iPriority
    int i=handle[iEntry.id];

    if (iEntry.priority>heap[i].priority)
    {
      // New priority is larger, so slide down
      heap[i].priority=iEntry.priority;
      heapify(i);
    }
    else
    {
      // New priority is smaller, so swap up
      heap[i].priority=iEntry.priority;
      swapUp(i);
    }
  }

  public void insert(heapEntry iEntry) throws minHeapFails
  {
    // Insert a new heap entry. 
    int j;

    if (full())
      throw new minHeapFails("Heap table size exceeded!");

    if (iEntry.id<0 || iEntry.id>=maxSub || handle[iEntry.id]!=(-1))
      throw new minHeapFails("id "+ iEntry.id+" issue for insert");

    j=(++n);  // Put next item into use

    // Swap the new item up the heap
    heap[j]=new heapEntry();  // Could implement Cloneable
    heap[j].priority=iEntry.priority;
    heap[j].id=iEntry.id;
    swapUp(j);
  }

  public void deleteId(int id) throws minHeapFails
  // Deletes the entry for id and frees its handle.
  {
    heapEntry work;
    int heapSlot,donor;

    if (id<0 || id>=maxSub || handle[id]==(-1))
      throw new minHeapFails("id "+id+" issue for delete");

    heapSlot=handle[id];
    handle[id]=(-1);
    donor=(n--);         // Last leaf element gets moved
    if (donor==heapSlot)
      return;

    // Next two lines transform the donation into a change of priority.
    heap[heapSlot].id=heap[donor].id;
    handle[heap[heapSlot].id]=heapSlot;
    changePriority(heap[donor]);
  }

  public heapEntry minimum() throws minHeapFails
  // Returns minimum element, but leaves it in the heap.
  {
    if (empty())
      throw new minHeapFails("Heap empty!");
    
    heapEntry work=new heapEntry();  // Could implement Cloneable
    work.priority=heap[1].priority;
    work.id=heap[1].id;
    return work;
  }

  public heapEntry extractMin() throws minHeapFails
  {
    heapEntry returnEntry;

    if (empty())
      throw new minHeapFails("Heap empty!");

    // Values being returned
    returnEntry=heap[1];
    handle[heap[1].id]=(-1); // Invalidate handle

    n--;  // Item is taken out of use
    if (empty())
      return returnEntry;

    // Last item (at highest-subscripted leaf) becomes the root and slides down.
    heap[1]=heap[n+1];
    heapify(1);
    return returnEntry;
  }

  public minHeap(int capacity)
  {
    heap=new heapEntry[capacity+1];
    handle=new int[capacity];

/*
    for (int i=0;i<capacity+1;i++)
      heap[i]=new heapEntry();
*/

    // Invalidate handles
    for (int i=0;i<capacity;i++)
      handle[i]=(-1);
    maxSub=capacity+1;
    n=0;
  }

  public minHeap(int capacity,int[] priorityIn,int count)
  // Constructs a heap using the provided priorities.
  // priorityIn[i] will have id i in the constructed heap,
  // so handle[i] may be used to track it.
  {
    int i;

    heap=new heapEntry[capacity+1];
    handle=new int[capacity];

/*
    for (i=0;i<capacity+1;i++)
      heap[i]=new heapEntry();
*/

    maxSub=capacity+1;
    n=count;
    // Caller should know conventions for ids and handles.
    for (i=0;i<count;i++)
    {
      heap[i+1]=new heapEntry(); // Create entries as needed
      heap[i+1].priority=priorityIn[i];
      heap[i+1].id=i;
      handle[i]=i+1;
    }
    // Invalidate unused handles
    for ( ;i<capacity;i++)
      handle[i]=(-1);

    // Sliding down starting from each node that is a parent,
    // in descending subscript (not priority) order.
    for (i=parent(n);i>0;i--)
      heapify(i);
  }

  public minHeap()
  {
    new minHeap(50);
  }

}