class Node
{
  int ind;
  Node nxt;

  public Node()
  {
    nxt = this;
  }

  public Node(int ind)
  {
    this.ind = ind;
  }
}

class PairingHeap
{
  private final static int MAXINT = Integer.MAX_VALUE;

  protected int      n;  // Maximum index value
  protected int[]  key;  // Keys of elements in heap
  protected Node[] pos;  // Pointer to node with given index
  protected Node[] chl;  // Pointer to children list of nodes
  protected Node   root; 

  public PairingHeap(int n)
  {
    this.n = n;
    key    = new int[n];
    pos    = new Node[n];
    chl    = new Node[n];
    for (int i = 0; i < n; i++)
      pos[i] = null;
    root = null;
  }

  public PairingHeap(int[] x, int n)
  {
    this(n);
    for (int i = 0; i < n; i++)
      insert(i, x[i]);
  }

  public PairingHeap(int x, int n)
  {
    this(n);
    for (int i = 0; i < n; i++)
      insert(i, x);
  }

  private Node link(Node h1, Node h2)
  // Link the heaps rooted at h1 and h2
  {
    if (key[h1.ind] > key[h2.ind])
    {
      Node dum = h1; h1 = h2; h2 = dum; 
    }

    // Hang h2 under h1 as new leftmost child
    h2.nxt = chl[h1.ind];
    chl[h1.ind] = h2;
    return h1;
  }

  public void decreaseKey(int i, int x)
  {
    key[i] = x;
    if (pos[i] != root)
    {
      Node h1 = pos[i];
      Node h2 = h1.nxt;
      if (h2.nxt == h2) // last node of list
      {
        pos[h1.ind] = h2;
        h2.ind = h1.ind;
        h1.nxt = h1;
      }
      else
      {
        pos[h1.ind] = h2; pos[h2.ind] = h1;
        int y = h2.ind; h2.ind = h1.ind; h1.ind = y;
        h1.nxt = h2.nxt;
      }
      root = link(pos[i], root);
    }
  }

  public void insert(int i, int x)
  {
    key[i] = x;
    pos[i] = new Node(i);
    chl[i] = new Node(); // sentinel
    if (root == null)
      root = pos[i];
    else
      root = link(root, pos[i]);
  }

  public boolean isEmpty()
  {
    return root == null;
  }

  public boolean isNotEmpty()
  {
    return root != null;
  }

  public int findMinKey()
  {
    if (root == null) 
      return MAXINT;
    return key[root.ind];
  }

  public int findMinInd()
  {
    if (root == null) 
      return -1;
    return root.ind;
  }

  public int deleteMinInd()
  {
    int x = root.ind;
    Node h1 = chl[root.ind];
    if (h1.nxt == h1) // root is the only element
      root = null;
    else
    {
      Node h2 = h1.nxt;
      Node h3 = h2.nxt;
      root = new Node(); // sentinel
      while (h2.nxt != h2)
      {
        h1 = link(h1, h2);
        h1.nxt = root;
        root = h1;
        h1 = h3;
        h2 = h1.nxt;
        h3 = h2.nxt;
      }
      if (h1.nxt != h1)
      {
        h1.nxt = root;
        root = h1;
      }
      h2 = root.nxt;
      h3 = h2.nxt;
      while (h2.nxt != h2)
      {
        root = link(root, h2);
        h2 = h3;
        h3 = h2.nxt;
      }
    }
    pos[x] = null;
    return x;
  }

  public int deleteMinKey()
  {
    return key[deleteMinInd()];
  }

  public int keyValue(int i)
  {
    return key[i];
  }

  public boolean inQueue(int i)
  {
    return pos[i] != null;
  }

  public void print()
  {
    System.out.println();
    if (root == null)
      System.out.println("PairingHeap is empty");
    else
    {
      System.out.println("Printing all nodes:");
      for (int i = 0; i < n; i++)
        if (pos[i] != null)
        {
          System.out.print("key[" + i + "] = " + key[i] + " list: ");
          Node h = chl[i];
          while (h.nxt != h)
          {
            System.out.print(h.ind + " ");
            h = h.nxt;
          }
          System.out.println();
        }
      System.out.println("Root index = " + root.ind);
    }
  }
}

public class PairingHeapTest
{
  public static void main(String[] args)
  {
    PairingHeap heap = new PairingHeap(20);
    heap.print();
    System.out.println("\nInserting 11 with key  9");
    heap.insert(11,  9);
    heap.print();
    System.out.println("\nInserting 13 with key  9");
    heap.insert(13,  9);
    heap.print();
    System.out.println("\nInserting  4 with key  8");
    heap.insert(4,  8);
    heap.print();
    System.out.println("\nInserting  3 with key  7");
    heap.insert(3,  7);
    heap.print();
    System.out.println("\nInserting 17 with key  5");
    heap.insert(17,  5);
    heap.print();
    System.out.println("\nInserting  1 with key  6");
    heap.insert( 1,  6);
    heap.print();
    System.out.println("\nInserting 12 with key  4");
    heap.insert(12,  4);
    heap.print();
    System.out.println("\nDecreasing  4 with key  5");
    heap.decreaseKey( 4,  5);
    heap.print();
    System.out.println("\nInserting  9 with key  6");
    heap.insert( 9,  6);
    heap.print();
    System.out.println("\nInserting  7 with key  8");
    heap.insert( 7,  8);
    heap.print();
    System.out.println("\nInserting  8 with key  1");
    heap.insert( 8,  1);
    heap.print();
    System.out.println("\nInserting  5 with key 11");
    heap.insert( 5, 11);
    heap.print();
    System.out.println("\nInserting 14 with key  7");
    heap.insert(14,  7);
    heap.print();
    System.out.println("\nDecreasing  4 with key  3");
    heap.decreaseKey( 4,  3);
    heap.print();
    System.out.println("\nDecreasing  3 with key  6");
    heap.decreaseKey( 3,  6);
    heap.print();
    System.out.println("\nDecreasing 12 with key  2");
    heap.decreaseKey(12,  2);
    heap.print();
    while (heap.isNotEmpty())
    {
      System.out.println("\nPerforming a deletemin");
      System.out.println("minInd = " + heap.deleteMinInd());
      heap.print();
    }

    System.out.println();
  }
}