клас Queue
Балансирано двоично дърво ви позволява бързо да намерите всеки сайт. Въпреки това, много приложения, които не изискват да получават произволно възел, а само минимум. Този проблем възниква, например, организацията, насочено търсене. Подходяща структура на данните за това ще бъде приоритет на опашката (приоритетна опашка).
Преди да обсъдим детайлите на организацията на приоритетната опашка, ние даваме пример за нейното използване (queue.js модул): В този пример приоритетната опашка 50 се поставя в поредица от случайни, вариращи от 0 до 99. След това, в една линия, докато елементите са изхвърлени от опашката в реда на увеличаване на стойността :
В допълнение към строителя, опашката за клас има 3 основни функции: unshift (N) - добавяне на всички от нов елемент N (движещ се "върне" големи елементи), промяна () - натискане на минимален елемент (измества всички "напред") и най-накрая, логическото функция празен () връща истина. ако опашката е празна (в противен случай - невярно).
Можете да запишете в приоритетната опашка е не просто число или низ, но също така и никакви предмети. За да направите това, вие трябва да замени функцията е по-малко от:
Организация дърво линия
Поръчайте приоритетна опашка възли в двоичен дърво. Това дърво две деца от всеки възел трябва да са по-големи или равни на възела родител. Съответно, в основата на дървото е най-малката единица. Тази организация на приоритетната опашка се нарича двоичен купчина. Под дърво линия на случайни числа от първия пример в предишния раздел на:
Възлите на дървото ще се съхраняват в петзвезден масив. корен възел е Аг елемент [1]. Двете потомци в AR [2] и Аг [3]. Потомство тата възлова точка (елемент Аг [Ь]) се съхранява в AR [2 * Ь] и Аг [2 * I + 1]. Чрез тази организация на данните, двоично дърво, както е балансиран. Ако броят на възли равна на дължината = 2 к -1. дървото ще бъде зает всички листа в долния (к -та) ниво. Като цяло, по-ниско ниво на дървото е изпълнен от ляво на дясно и в ар [дължината] е най-дясната ниско ниво възел. Аг нула елемент масив не се използва. По-долу е двоично дърво и съответната му представяне под формата на масив (имайте предвид, че елементите в масива са в порядъка на дървото на преминаването от горе до долу и от ляво на дясно):
Добавяне на елемент към опашката
Добавянето - сравнително проста работа. Новият възел на дървото се поставя за първи път в най-долната част него. За да направите това, трябва само да вмъкнете нов възел за последния възел в масива (на първия ред на функцията). Припомнете си, че ако ++ стои пред променлива, първият се увеличава с единица (по-долу, това се увеличи броят на възли ++ this.length дърво), и след това участва в експресията: е последният елемент на масива, възелът става дете възел с дължина индекс / 2 === и >> 1 ( "число участък"). След това е необходимо да се издигне на дървото до корена (взаимозаменяемост с възли майки в места), стига да е по-малък, отколкото майка. Операцията е по-малко, отколкото се използва функцията по подразбиране: пермутация функция на аз-ти и к-тия елемент на АБ на масива е както следва:
По-долу са последователни стъпки за добавяне на нов възел на стойност от 2, и нейното повдигане на определеното място за него:
Popping на елемент от опашката
За да извадите минимален елемент от опашката, направете следното. Първа смяна в основата и на последния възел на дървото. След това, бившият корен (минималната единица) може лесно да се отстрани чрез намаляване на броя на възлите length--. Въпреки това, бивш последния възел, който е фундаментално нарушава свойствата на дърво. Поради това, тя трябва да се спуснат, промяна на места с техните потомци, а той няма да вземе "правилното" място на дървото. Това се случва, когато и двете му деца ще бъдат по-големи или равни пропускат възел. По време на спускане се променя възел от минимум две деца, се е повишила до над минималната стойност. По-долу е пример, в който се спуска надолу ключ 5 след обмен с корен 1:
Подходящ функция код промяна е: Тя използва от "почистване" на дървото, като се започне с възел на възела и по-долу:
С помощта на двоичен купчина - е най-лесният начин за организиране на приоритетна опашка. В подкрепа на свойствата на купчина, когато поставяте или бутане възел се изисква среден операции log2 N, където N - брой на възли в дървото. За сметка на някои усложнения, е възможно да се получи единица сложност O (1) добавяне на (т.е. скоростта на прибавяне не зависи от броя на възли). Това запазва логаритмична отстраняването на сложност възел. Съответната структура данни, наречена купчина Фибоначи.
Имайте предвид, че приоритетната опашка в същото време е начин за сортиране (някои набор от ценности поставена в опашката, където вече е премахнат в дадения ред).
Свързани статии