// This code is from "Algorithms in Java, Third Edition,"
// by Robert Sedgewick, Addison-Wesley, 2003.

// See program 9.12 index-heap-based priority queue

class intPQi 
{
  private int[] a;

  private int[] pq, qp; 

  private int N, maxQueued;

  intPQi(int[] items,int m)
  {
    a = items;    // Save reference to index table
    maxQueued=m;
    N = 0; 
    pq = new int[maxQueued+1]; // Contains subscripts to a[]
    qp = new int[a.length];    // Inverse of pq, allows changing priorities
  }

  private boolean less(int i, int j)
  { return a[pq[i]] < a[pq[j]]; }

  private void exch(int i, int j)
  {
    int t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
    qp[pq[i]] = i;
    qp[pq[j]] = j; 
  }

  private void swim(int k)
  // Program 9.3
  {
    while (k > 1 && less(k/2, k))
    {
      exch(k, k/2);
      k = k/2;
    }
  }

  private void sink(int k, int N)
  // Program 9.4
  {
    while (2*k <= N)
    {
      int j = 2*k;
      if (j < N && less(j, j+1))
        j++;
      if (!less(k, j))
        break;
      exch(k, j);
      k = j;
    }
  }

  boolean empty()
  { return N == 0; }

  boolean full()
  { return N == maxQueued; }

  void insert(int v)
  {
    pq[++N] = v;
    qp[v] = N;
    swim(N);
  }

  int getmax()
  {
    exch(1, N);
    sink(1, N-1);
    return pq[N--];
  }

  void change(int k)
  {
    swim(qp[k]);
    sink(qp[k], N);
  }
}