СРАВНЕНИЕ НА ДИНАМИЧЕН МАСИВ, ТАБЛИЦА, ДВОИЧНО НАРЕДЕНО ДЪРВО И ПИРАМИДА///
1.ДОБАВЯНЕ НА ЕЛЕМЕНТ
МАСИВ-push_back()
Вкарва нов елемент в края на вектора. Забележете, че ако заделената памет вече е запълнена, преди да вкараме елемента, трябва да разширим вектора.push_front()
Вкарва нов елемент в началото на вектора. За целта първо го разширяваме (ако трябва), а после преместваме всичките му досегашни елементи с един надясно (за да освободим място за новия в началото), тоест тази операция е "скъпа" откъм време.
ТАБЛИЦА-Добавяне на елемент
Добавянето на елемент става като първо го хешираме, за да знаем на коя позиция да го сложим, след което обходим вектора в тази позиция за да проверим дали елементът случайно не е вече в хештаблицата (в който случай просто променяме стойността му). В случай, че не сме го намерили, го добавяме във вектора с обектите с тази хеш стойност.О(1)
Търсене на елемент
Търсенето на елемент ще правим в две части: в първата ще хешираме ключа, а във втората ще го търсим линейно във вектора, който бива сочен от този хеш.Премахване на елемент
Премахването на елемент не е особено по-различно от търсенето, но накрая премахваме елемента.
ХИЙП- Добавяме новия елемент като ново листо на дървото. Тъй като дървото е пълно или почти пълно двоично дърво, то това е еквивалентно да го сложим просто на позиция size в масива, където size е текущият брой елементи. Ако ползваме vector, това не е нищо повече от heap.push_back(newElement).В този момент е възможно двоичното дърво да няма желаните свойства за пирамида (например, представете си, че сме добавили елемент с много висок приоритет, който трябва да отиде на върха). За да възвърнем тези му свойства, ще бутаме елемента нагоре в дървото, докато не се случи едно от следните две:
Елементът стане корен на дървото;
или
Текущият му баща е по-голям или равен на него.Ако в пирамидата е имало N елемента, следователно дървото ѝ има log(N) нива. Тъй като движим новия елемент единствено нагоре, то сложността на тази операция е O(logN).
При приоритетната опашка обикновено единственият елемент, който бихме премахвали, е този с максимална стойност, тъй като той е единственият, за който знаем точната му наредба спрямо всички останали. Затова тук считаме, че ще премахваме само корена.
ДВОИЧНО ДЪРВО- За да добавим нов елемент в дървото, първо трябва да намерим неговата позиция - към кой връх да го закачим. Сходно на търсенето, ще се спускаме надолу към дървото докато стигнем връх, в който можем да го добавим като дете (ляво, ако върхът е по-голям, и дясно в противен случай). Създаваме новия връх и го свързваме в дървото.
Премахване на елемент
Премахването на елемент е малко по-сложно, тъй като искаме да запазим дървото "двоично" - тоест с максимум два наследника от всеки връх. Отново пускаме търсене в дървото. Има няколко случая:
1Ако търсенето не намери връх с тази стойност, то няма какво да премахваме и приключваме (стойността, която искаме да премахнем, я няма и без друго).
2Ако търсенето намери връх с тази стойност и този връх няма деца, директно го премахваме. Отбелязваме в бащата му, че въпросният син вече не съществува.
Ако търсенето намери връх с тази стойност и този връх има едно дете, то премахваме върха и закачаме детето му (съответно под-дървото с корен това дете) към бащата му вместо премахнатия връх.
3Ако търсенето намери връх с тази стойност и този връх има две деца, то трябва някак да закачим и двете деца за бащата на върха. Тъй като това е невъзможно, вместо това ще сложим друг връх от дървото на мястото на сегашния, запазвайки свойствата на дървото. Този връх трябва да е такъв, че всички върхове в под-дървото на лявото дете да са по-малки от него и всички върхове, в под-дървото на дясното дете да са по-големи или равни. Един връх, който изпълнява тези изисквания, е най-малкият в под-дървото на дясното дете.
Търсене на елемент
За да намерим елемент (връх от дървото), почваме от корена и се спускаме надолу по децата, докато намерим този, който ни трябва (или видим, че такъв няма). На всяка стъпка:
Ако стойността на текущия връх е тази, която търсим, спираме.
Ако стойността на текущия връх е по-голяма от тази, която търсим, отиваме в лявото дете. Ако такова дете няма, то значи търсеният елемент не присъства в дървото.
Ако стойността на текущия връх е по-малка от тази, която търсим, отиваме в дясното дете. Ако такова дете няма, то значи търсеният елемент не присъства в дървото.