Queap

QueapVelut Anglicum queue 'cauda' + heap 'congeries'; ergo Latine plene explicatum congeries caudalis.  (portmanteau Anglicum, a Ioanne Iacono et Stephano Langerman excogitatumJohn Iacono et Stefan Langerman, Queaps, Algorithmica 42(1):49–56 (2005).) 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.

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

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

Notae

Categoria:Informatica
Categoria:Neologismi
Categoria:Verba Anglica