Queap

E Vicipaedia
Jump to navigation Jump to search
Queap Q cum k = 6 et n = 9.

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.

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[recensere | fontem recensere]

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

Notae[recensere | fontem recensere]

  1. Velut Anglicum queue 'cauda' + heap 'congeries'; ergo Latine plene explicatum congeries caudalis.
  2. John Iacono et Stefan Langerman, Queaps, Algorithmica 42(1):49–56 (2005).
computatorum Haec stipula ad informaticam spectat. Amplifica, si potes!
mathematica Haec stipula ad mathematicam spectat. Amplifica, si potes!