Implementación de Binary Heap en Java: Montículo binario

Electricidad y Electrónica4,3 KB

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));
        }
    }
}

Descargar

PDF Word HTML