Implementación de Binary Heap en Java: Montículo binario
Implementación dun montículo binario (Binary Heap) en Java
Exemplo completo de código para unha estrutura de datos de tipo Binary Heap que implementa a interface PriorityQueue:
public class BinaryHeap<T extends Comparable<T>> implements PriorityQueue<T> {
protected T[] elementos;
private int numElementos;
private final static int DEFAULT_SIZE = 7;
private int max;
public BinaryHeap() {
elementos = (T[]) new Comparable[DEFAULT_SIZE];
numElementos = 0;
max = DEFAULT_SIZE;
}
public BinaryHeap(int n) {
elementos = (T[]) new Comparable[n];
numElementos = 0;
max = n;
}
public boolean add(T elemento) {
if (elemento == null || estaEnCola(elemento)) return false;
if (numElementos == 0) {
elementos[0] = elemento;
numElementos++;
return true;
} else {
elementos[numElementos - 1] = elemento;
numElementos++;
recolocar(elemento);
return true;
}
}
public T poll() {
if (numElementos == 0) throw new IllegalStateException("Non se pode operar, o montículo está baleiro.");
T aux = elementos[0];
remove(elementos[0]);
return aux;
}
public boolean remove(T elemento) {
if (elemento == null || getPos(elemento) == -1 || numElementos == 0) return false;
if (elementos[numElementos - 1] == elemento) {
elementos[numElementos - 1] = null;
numElementos--;
return true;
} else {
int pos = getPos(elemento);
intercambiar(elemento, elementos[numElementos - 1]);
elementos[numElementos - 1] = null;
int hm = PosHijoMenor(pos);
while (elementos[hm].compareTo(elementos[pos]) > 0 && hm != -1) {
intercambiar(elementos[pos], elementos[hm]);
pos = hm;
hm = PosHijoMenor(pos);
}
}
numElementos--;
return true;
}
public boolean isEmpty() {
if (numElementos == 0) {
return true;
}
return false;
}
public void clear() {
for (int i = 0; i < numElementos; i++) {
elementos[i] = null;
}
numElementos = 0;
}
public int getNumElementos() {
return numElementos;
}
private T find(int pos) {
if (pos >= numElementos)
return null;
return elementos[pos];
}
private int PosHijoMenor(int pos) {
T elem = find(pos);
if (elem == null) return -1;
int hd = getHijoDerecho(elem);
int hi = getHijoIzquierdo(elem);
if (hd == -1 || hi == -1) return -1;
if (find(hi).compareTo(find(hd)) > 0)
return hd;
return hi;
}
private int getHijoDerecho(T elem) {
int pos = getPos(elem);
if (elementos[(2 * pos) + 2] == null) return -1;
int hijo = getPos(elementos[(2 * pos) + 2]);
if (find(hijo) == null)
return -1;
return hijo;
}
private int getHijoIzquierdo(T elem) {
int pos = getPos(elem);
if (elementos[(2 * pos) + 1] == null) return -1;
int hijo = getPos(elementos[(2 * pos) + 1]);
if (find(hijo) == null)
return -1;
return hijo;
}
private int getPadre(int pos) {
return (pos - 1) / 2;
}
private int getPos(T elem) {
for (int i = 0; i < numElementos; i++) {
if (elementos[i] == elem)
return i;
}
return -1;
}
private void intercambiar(T elem1, T elem2) {
int pos1 = getPos(elem1);
int pos2 = getPos(elem2);
T aux = elementos[pos1];
elementos[pos1] = elementos[pos2];
elementos[pos2] = aux;
}
private void recolocar(T elem) {
int padre = getPadre(getPos(elem));
if (find(padre).compareTo(elem) > 0 || find(getPadre(getPos(elem))) == null) { // O método find devólvenos o nodo dunha posición.
intercambiar(find(padre), elem);
}
}
private void recolocarTodo() {
for (int i = numElementos; i == 0; i--) {
recolocar(find(i));
}
}
}