Java Priority Queue Implementation: Linked List and Binary Heap for Student Ranking

Priority Queue Implementations in Java

This page presents two implementations of a priority queue for student records (ALUNO), each based on the FilaPriA interface. The first uses a dynamic linked list, and the second uses a binary heap stored in an array.

Dynamic Linked List Implementation

The class FilaPriDinamicaAlunos implements FilaPriA using a linked list of nodes sorted by classification in descending order.

public class FilaPriDinamicaAlunos implements FilaPriA {
    protected class No {
        ALUNO val;
        No seg;
    }

    protected No prox;
    protected ALUNO ITEM_NOT_FOUND;

    public void inicial() {
        prox = null;
    }

    public void coloca(ALUNO n) {
        No aux = new No();
        aux.val = n;
        No ant = null, pos = prox;
        while (pos != null && pos.val.getclassif() > n.getclassif()) {
            ant = pos;
            pos = pos.seg;
        }
        if (ant == null) {
            aux.seg = pos;
            prox = aux;
        } else {
            ant.seg = aux;
            aux.seg = pos;
        }
    }

    public void retiramaior() {
        if (prox != null)
            prox = prox.seg;
        else
            throw new IllegalStateException("Erro: fila prioritaria vazia!");
    }

    public ALUNO maior() {
        if (prox != null)
            return prox.val;
        throw new IllegalStateException("Erro: fila prioritaria vazia!");
    }

    public boolean vazia() {
        return prox == null;
    }
}

Binary Heap Implementation (Exercise 32b)

The class FilaPriHeapAlunos stores elements in a fixed-size array with a capacity of lim = 100. Insertion uses percolate up, while removal uses percolate down.

public class FilaPriHeapAlunos implements FilaPriA {
    protected static final int lim = 100;
    protected ALUNO[] ve = new ALUNO[lim + 1]; /* matriz de elementos */
    protected int n_elementos; /* indicador de ocupacao da matriz */

    public void inicial() {
        n_elementos = 0;
    }

    public void coloca(ALUNO al) {
        if (n_elementos != lim) {
            int posicao = ++n_elementos;
            // percolate up
            while (posicao > 1 && al.getclassif() > ve[posicao / 2].getclassif()) {
                ve[posicao] = ve[posicao / 2];
                posicao = posicao / 2;
            }
            ve[posicao] = al;
        } else {
            throw new IllegalStateException("Erro: capacidade da fila prioritaria excedida!");
        }
    }

    public ALUNO maior() {
        if (n_elementos != 0)
            return ve[1];
        throw new IllegalStateException("Erro: fila prioritaria vazia!");
    }

    public void retiramaior() {
        if (n_elementos != 0) {
            // percolate down
            ALUNO aux = ve[n_elementos--];
            int posicao = 1, maiordescendente;
            boolean auxmenorquedescendentes = true;
            while (posicao * 2 <= n_elementos && auxmenorquedescendentes) {
                maiordescendente = posicao * 2;
                if (maiordescendente != n_elementos &&
                    ve[maiordescendente + 1].getclassif() > ve[maiordescendente].getclassif())
                    maiordescendente++;
                if (aux.getclassif() <= ve[maiordescendente].getclassif()) {
                    ve[posicao] = ve[maiordescendente];
                    posicao = maiordescendente;
                } else {
                    auxmenorquedescendentes = false;
                }
            }
            ve[posicao] = aux;
        } else {
            throw new IllegalStateException("Erro: fila prioritaria vazia!");
        }
    }
}