public class PriorityQueue {

class HNode {
	int nod;
	int key;
	
	public HNode(int i,int k) {
	nod = i;
	key = k;
	}
}


public HNode[] heapArray;
int length;
int heap_size;


	PriorityQueue(int l, int d[]) {
	   heapArray = new HNode[l];
	   for(int i=1;i < l;i++) 
	   		heapArray[i] = new HNode(i,d[i-1]);
	    length = l;
	   heap_size = l-1;	
	   makeHeap();	
	  
	}		  		

	int right(int i) { return 2*i;} 
	
	int left(int i) { return 2*i+1;}//(i<<2)|1 
	
	int parent(int i) { return i/2;} 
	 
	void heapify(int poz) {
		int minim;	
		HNode inter = new HNode(0,0);
		if(right(poz) <= heap_size && heapArray[right(poz)].key < heapArray[poz].key) minim = right(poz);
			else minim = poz;
		if(left(poz) <= heap_size && heapArray[left(poz)].key < heapArray[minim].key) minim = left(poz);
		if (minim != poz) {
			inter = heapArray[poz];
			heapArray[poz] = heapArray[minim];
			heapArray[minim] = inter;
			heapify(minim);
			} 
		}
	
	int extractMin() {
  		int minim = 0;
		if (heap_size < 1) return -1;
			minim = heapArray[1].nod;
			heapArray[1] = heapArray[heap_size];
			heap_size--;
			heapify(1);
			
		return (minim - 1);
	}
	
	int getMin() {
		return heapArray[1].key; 
	}
		
	
	void makeHeap() {
	  for(int i=(heap_size)/2;i >= 1;i--) 
		heapify(i);	
	}		 	 	
	
	int heapSize() { return heap_size;}
	


}