public class Heap {

    int size;
    int key[];
    Vertex node[];

    public Heap() {
	size = 0;
	key = new int[100];
	node = new Vertex[100];
    }

    public boolean not_empty () {
	if (size > 0) 
	    return true;
	else 
	    return false;
    }

    public void up_heap(int v) {
	int u;
	int k;
	Vertex n;
	while (v != 0) {
	    u = (v +1) / 2 -1;
	    if (key[u] >=  key [v]) {
		k = key[u];
		key[u] = key[v];
		key[v] = k;

		n = node[u];
		node[u] = node[v];
		node[v] = n;
		node[u].Q_pos = u;
		node[v].Q_pos = v;

	    }
	    else {
		break;
	    }
	    v = u;
	}
    }

    public void down_heap (int r) {
	int s;
	int k;
	Vertex n;

	while (r * 2 +1 < size ) {
	    if (r*2 + 2 >= size ) {
		s = r*2 + 1;
	    }
	    else if (key[r*2+1] < key[r*2+2]) {
		s = r*2 + 1;
	    }
	    else {
		s = r*2 + 2;
	    }

	    if (key[r] > key[s]) {
		k = key[r];
		key[r] = key[s];
		key[s] = k;

		n = node[r];
		node[r] = node[s];
		node[s] = n;
		node[r].Q_pos = r;
		node[s].Q_pos = s;

	    }
	    else {
		break;
	    }
	}
    }


    public void add_node(int k, Vertex n) {
	int i;
	key[size] = k;
	node[size]= n;
	n.Q_pos = size;
	up_heap(size);
	size++;
    }

    public Vertex extract_min () {
	Vertex u;
	if (size == 0) 
	    return null;

	u = node[0];
	key[0] = key[size-1];
	node[0] = node[size-1];
	size--;
	down_heap(0);
	u.in_Q = false;
	return u;
    }

}