Qуеап

У информатици, "qуеап" је ред са приоритетом. Овај тип података дозвољава убацивање и брисање елемената, а подржава и враћање елемента највећег приоритета. Свако брисање траје логаритамски у односу на број елемената који су дуже у структури од елемента који брисемо. Убацивање је константне временске сложености.

Ова структура података се састоји од дупло повезане листе и 2-4 стабла, где су обе структуре модификоване да прате елемент минималног приоритета. Основне операције ове структуре одржавају додате елементе у дупло повезану листу, док се не изврши брисање елемента, када се сви елементи сместе у 2-4 стабло. 2-4 стабло чува своје елементе у инсертном поретку уместо у погоднијем поретку приоритета.

Овај тип података су осмислили и именовали Јохн Иацоно и Стефан Лангерман.

Опис

Qуеап је ред са приоритетом у који се елементи убацују у О(1) времену, а бришу минимални елементи у О(лог(к+2)) времену ако има к елемената који су били у хипу дуже од елемента који се брише. Qуеап има својство које се зове својство qуеап-а: време које је потребно да се нађе неки елемент x је О(лг(q(x))) где је q(x) једнако н-1-w(x) а w(x) је број елемената којима је приступљено операцијама као сто су операција претраге, брисања или убацивања. q(x) се дефинисе као број елемената којима није приступано од последњег приступа елементу x. Време за проналажење елмента је О(лг(w(x))).

Qwеап се мозе представити преко два типа података: дупло повезане листе и модификоване верзије 2-4 стабла. Дупло повезана листа се користи за инструкције убацивања и лоцирања минималног елемента. Qуеап чува показивач на минимални елемент у листи. Да би се додао неки елемент у листу, тај елемент се додаје на крај листе и битовска варијабла у том елементу се поставља на један. Ово се врши како би се знало да ли је елемент у листи или 2-4 стаблу.

2-4 стабло служи када се врши операција брисања. Ако је елемент већ у стаблу, елемент се брисе из 2-4 стабла. Иначе, елемент је у листи(проверава се преко битовске варијабле).Сви елементи садржани у листи су онда додају у 2-4 стабло, успут постављајући битовске варијабле на нуле.Елемент је тад одстрањен из стабла.

Qуеап користи само својства 2-4 стабла, не и стабло претраге. 2-4 стабло се модификује на следећи начин. Претпоставимо да листа има скуп од к елемената. Када се операција брисања позове, скуп елемената сачуван у листи се онда додаје на листове 2-4 стабла,настављајући се листом који садржи кључ бесконацности. Сваки интернодални чвор стабла има показивац х(в) који показује на најмањи елемент подстабла в. Сваки интернодални чвор на путу П од корена има показивац ц(в), који показује на најмањи кљуц у $T-T_{v}-\{r\}$. х(в) показиваци на сваки интернодални цвор на путу П се игнорису. Qуеап има показивац на ц од корена који показује на најањи елемент.

Апликација qуеапова укљуцује јединствени скуп догађаја великих приоритета и издвајања догађаја великих приоритета за обраду.

Операције

Нека МинЛ буде показивач на минимални елемент у дупло повезаној листи L, а ц(x0) буде минимални елемент чуван у 2-4 стаблу Т,к нек буде број елемента цуваних у 2-4 стаблу Т и нека н буде број свих елемената у qуеап-у Q. Операције су следеце:

Неw(Q): Ствара нови празни qуеап.

Ствара празну дупло повезану листу L и 2-4 стабло Т. к и н су нула.

Инсерт(Q,x): Додаје елемент x на qуеап Q.

Додаје елемент x у листу L. Поставља битовску варијаблу елемента x на један да би се знало да је елемент у листи L. Азурира се минЛ показивач ако је x најмањи елемент у листи. Повећавамо н за један.

Минимум(Q): Враћа показивач на најмањи елемент из Qуеап-а Q.

Ако кључ(минЛ) < кључ(ц(x0)), врати минЛ.Иначе врати ц(x0).

Делете(Q,x): Одстрањује елемент x из qуеап-а Q.

Ако је бит елемента постављен на један, елемент се налази у листи L. Додају се сви елементи из L у Т, постављајући бит сваког елемента на нулу. Сваки елемент се додаје родитељу најдеснијег детета од Т користеци операцију додавања елемената у 2-4 стабло. L постаје празан. Ажурира х(в) показиваце на све чворове чија су деца сад модификована, и понавља процес са следећим родитељем докле год родитељ није корен. Хода се од корена ка чвору x0 и ажурирају се ц(в) вредности. к је једнако н.

Ако је бит елемента x нула, x је онда лист од Т. Брисе се x користећи операцију за брисање елемената у 2-4 стаблу. Почевши од чвора x, хода се у Т до чвора x0, ажурирајући х(в) и ц(в) показиваче. Смањују се к и н за 1.

ДелетеМин(Q):Брише се и враћа најмањи елемент из qуеап-а Q.

Позива се операција Минимум(Q). Операција враћа најмањи елемент мин. Позива се операција Делете(Q,мин).Враца мин.

ЦлеанУп(Q): Брише све елементе у листи л и стаблу Т.

Почевси од првог елемента у листи L, прелази се цела листа,бришући се елементи исте.

Почевси од корена стабла Т, прелази се стабло, бришући се сваки чвор из стабла.

Анализа

Време извршавања се анализира коришћењем амортизоване анализе. Потенцијална функција за qуеап Q ће бити $\phi (Q)=c|L|$ где је $Q=(T,L)$. Инсерт(Q,x): Цена операције је О(1).Велицина листе расте за један, потенцијал расте за неку константу ц. Минимум(Q): Ова операција не мења структуру тако да је амортизована цена једнака правој цени, О(1). Делете(Q,x):Постоје два случаја.

Први случај

Ако је елемент x у стаблу Т, онда је цена О(1). Чим је елемент обрисан из стабла, показивачи морају да се ажурирају. Највише ће бити О(лг q(x)) ажурирања.

Други случај

Ако је елемент у листи, онда се сви елементи из листе L смештају у стабло Т. Цена овога је $a|L|$ од неке константе а. После убацивања и ажурирања показивача, време које је потрошено је $2a|L|$. Следи брисања елемента из стабла, и шетња кроз стабло са успутним кориговањем показивача. Време потрошено је највише $2a|L|+O(lgq(x))$. Ако је ц>2а онда је цена О(лгq(x)).

Пример кода

Пример имплементације qуеап-а у јави:

public class Queap
{
        public int n, k;
        public List<Element> l; //Element is a generic data type
        public QueapTree t;    //a 2-4 tree, modified for Queap purpose
        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 is a 2-4 tree and x0, cv are tree nodes.
                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) {
                        //set inList of all the elements in the list to false
                        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;
        }
}

Види још

• Листа (структура података)
• 2-3-4 стабло