BinaryHeap no problema da mochila

Olá, a minha dúvida é como implementar o binary heap no problema da mochila, eu tenho a base do programa, mas preciso que ele funcione com o binary heap, andei perguntando e me disseram que a única coisa que devo mudar é o método insert e o removeTop, mas sinceramente não tenho idéia de como fazer isso, será que alguém pode me ajudar :?:

O código:

import java.util.Scanner;

class Objeto implements Comparable<Objeto> {
	public String nome;
	public float valor, peso;
	public float frac;
	
	Objeto(String desc, float v, float p) { nome = desc; valor = v; peso = p; }
	public int compareTo(Objeto x) {
		float q = valor/peso - x.valor/x.peso;
		if (q > 0) return 1;
		if (q < 0) return -1;
		return 0;
	}
}

class PQueue<T extends Comparable<? super T>> {
	private T [] array;
	private int pSize;
	
	public PQueue(int n) {
		pSize = 0;
		array = (T[]) new Comparable[n+1];
	}
	
	public void insert(T o) {
		array[pSize++] = o;	
	}
	
	public boolean isEmpty() {
		return pSize == 0;
	}
	
	public T removeTop() {
		int m = 0;
		for(int k = 1; k < pSize; k++)
			if (array[m].compareTo(array[k]) == -1) m = k;
		T o = array[m];
		array[m] = array[--pSize];
		return o;
	}
	
}
	
class FracKnap {
	
	public static void fracknap(PQueue<Objeto> p, float K) {
		while (!p.isEmpty()) {
			Objeto o = p.removeTop();
			if (o.peso <= K) {
				o.frac = 1;
				K -= o.peso;
			}
			else {
				o.frac = K/o.peso;
				K = 0;
			}
		}
	}
	
	public static void main(String [] args) {
		Scanner in = null;
		try {
			in = new Scanner(System.in);
			int n = in.nextInt();
			float K = in.nextFloat();
			Objeto [] obj = new Objeto[n];
			PQueue<Objeto> p = new PQueue<Objeto>(n);
			for (int i = 0; i < n; i++) {
				String s = in.next();
				float peso = in.nextFloat();
				float valor = in.nextFloat();
				obj[i] = new Objeto(s, valor, peso);
				p.insert(obj[i]);
			}
			fracknap(p, K);
			for (int i = 0; i < n; i++)
				System.out.println(obj[i].nome + " " + obj[i].frac);
		} finally {
			if (in != null) {
				in.close();
			}
		}
	}
}

Desde já, muito obrigado :wink:

Topicos relacionados