Queap

Queap^[1] (portmanteau Anglicum, a Ioanne Iacono et Stephano Langerman excogitatum^[2]) in scientia computatrali est cauda prioritatis structurae datorum quae minimam indicat rem coacervatam. Queap ex indice bis nexato et arbore 2–4 structurae datorum constat. Structura datorum proprietatem queapicam explet, complementum proprietatis copiarum laborantium, quod efficit ut operationes cuiusdam elementi x in O(lgq(x)) tempore amortizato computentur ubi q(x) est rerum numerus qui in cauda prioritatis diutius quam x fuit.

Queap Q cum k = 6 et n = 9.

Index bis nexatus elementa k inserta perscribit. Cum operatio delens fiat, res k arbori 2–4 adduntur; minima res tum ab arbore removetur. Quaeque structura minimam rem indicat. Arbor 2–4 tam pro hac structura mutata est ut minima elementa tempore constanti accedantur.

Exemplum codicis

Parva cuiusdam queap instrumentatio Java:

public class Queap
{
        public int n, k;
        public List<Element> l; //Elementum est genericum datorum genus
        public QueapTree t;    //arbor 2-4, pro queap mutata
        public Element minL;

        private Queap() {
                n = 0;
                k = 0;
                l = new LinkedList<Element>();
                t = new QueapTree();
        }

        public static Queap New() {
                return new Queap();
        }

        public static void Insert(Queap Q, Element x) {
                if (Q.n == 0)
                        Q.minL = x;
                Q.l.add(x);
                x.inList = true;
                if (x.compareTo(Q.minL) < 0)
                        Q.minL = x;
        }

        public static Element Minimum(Queap Q) {
                //t est arbor 2-4 et x0, cv sunt nodi arborei
                if (Q.minL.compareTo(Q.t.x0.cv.key) < 0)
                        return Q.minL;

                return Q.t.x0.cv.key;
        }

        public static void Delete(Queap Q, QueapNode x) {
                Q.t.deleteLeaf(x);
                --Q.n;
                --Q.k;
        }

        public static void Delete(Queap Q, Element x) {
                QueapNode n;
                if (x.inList) {
                        //copia inList omnium elementorum in indice ad falsum
                        n = Q.t.insertList(Q.l, x);
                        Q.k = Q.n;
                        Delete(Q, n);
                }
                else if ((n = Q.t.x0.cv).key == x)
                        Delete(Q, n);
        }

        public static Element DeleteMin(Queap Q) {
                Element min = Minimum(Q);
                Delete(Q, min);
                return min;
        }
}

Nexus interni

• Arbor dilatata
• Arbor 2-4
• Cauda (structura datorum)
• Cauda prioritatis
• Explicatio amortizata
• Index bis nexatus