Сортирането на данни е изключително важно за организиране на данни и за търсене на запис по-късно в сортираните данни. Добър алгоритъм, известен за сортиране днес, е сортирането чрез сливане, което отнема O(nlogn) време. За големи набори от данни това време може да бъде много дълго и следователно неефективно. По този начин, в случай на големи набори от данни, където повечето от елементите попадат в определен диапазон, да речем от 0 до u-1, можем да ги сортираме във времето O(nloglogu)(тук n-брой елементи и u-диапазон, в който всички n числа попадат в). Интересно, нека да видим как се прави.

Дървото Van Emde Boas се използва за сортиране на такива данни. Също така се основава на подхода „разделяй и владей“, като алгоритъма за сортиране чрез сливане, но тук диапазонът е разделен на блокове с размер √u. Всеки блок се нарича галактика или клъстер. По този начин има √uгалактики, всяка с размер √u. Нека да получим ясна картина с пример. Да приемем, че n={0,1,8,9,10,11,14}. Минималните и максималните елементи в списъка са 0 и 15. Така диапазонът ще бъде от 0 до 15. Представяме наличието на число в структурата с ‘1’ и липсата с ‘0’.

Разделете диапазона на √u(тук √16=4) галактики. Тук всяка галактика отново се смята за структура на Ван Емде Боас . За разграничаване на празни и непразни галактики се използва обобщена структура. Една галактика има стойност 1 в обобщение, ако има един или повече елементи, в противен случай 0.Входът на обобщената структура за всяка галактика може да бъде изчислен чрез извършване на операция „или“. Първо вземете всеки два елемента в галактика и изчислете „или“, по-късно изпълнете „или“ за стойности, генерирани на всяко ниво, докато получите една единствена стойност за галактика. Това прави обобщената структура с размер √u.

Сега ще се опитаме да анализираме как да извършим вмъкване и намиране на наследник на дадено число. Анализът им помага да се разбере техниката на сортиране. Първо нека видим вмъкването. Ако e е елементът, който трябва да се вмъкне, намираме неговата позиция по формулата: e=i√u+j, където i е номерът на галактиката, а j е позицията на e в галактиката i. Вземете пример 10 (да приемем, че не е вмъкнат). 10/√16=2 и 10%√16=2. По този начин 10 се намира в позиция 2 (приемете базиран на нула индекс) в галактика 2. Тук дефинираме две функции, за да знаем номера на галактиката и позицията в галактиката, които са high(e)=e/√u и low(e)=e%√u. Освен това дефинираме функцията compute, за да се върнем към e като compute(i,j)=i√u+j.

Терминология: v-Van Emde Boas структура

v.galaxy[i]- Всяка галактика е представена като малка структура на Van Emde Boas с размер √u.(0≤i≤√u)

v.резюме-размер√u. Първоначално се поддържа нула, докато не бъде вмъкнато произволно число.

v.min- минималният елемент на v или нула, ако е празен

v.max-максималния елемент на v или нула, ако е празен

Процес на вмъкване:Ако има функция Insert(v,e)(e е елементът за вмъкване), извършваме рекурсивни извиквания към нея. Първоначално проверяваме дали v.min е null, след което структурата е празна, така че инициализираме v.min и v.max на e и се връщаме. Ако v.min ›e, тогава разменяме e и v.min. Ако v.max‹e, актуализирайте v.max=x. Ако v.galaxy[high(e)].min==null, тогава рекурсивно извикайте вмъкване на v.summary и high(x), за да актуализирате резюмето (Тъй като горните условия правят необходими вмъквания, ние актуализираме резюмето, за да покажем, че тази галактика сега не е празен). И накрая, ако резюмето вече е актуализирано (т.е. искаме да вмъкнем елементи в галактика, която не е празна), тогава директно извикайте рекурсивната функция на v.galaxy[high(e)] и low(x).

Процес на намиране на наследник: Дефинираме функция find(v,e) (e е елементът, за който трябва да се намери наследник), за да намерим наследник. Ако e‹v.min, тогава v.min е наследник, следователно връщаме v.min. Сега инициализирайте x като high(e). Ако low(e)‹v.galaxy[i].max(тук проверяваме дали галактиката, в която се намира елементът e, има елемент до него.), тогава y=find(v.galaxy[x],low( e)) иначе направете x=find(v.summary,high(e)) и y=v.galaxy[x].min и върнете compute(i,j)(тук, ако не можем да намерим наследник в галактиката на елемент e , проверяваме обобщено за следващите налични елементи в други галактики, ако намерим галактика, тогава приемаме първия елемент в нея като наследник на e и функцията compute() изчислява стойността на приемника).

Времеви сложности:

Във всички случаи на вмъквания и намиране на наследници получаваме рекурентна връзка:

T(n)=T(√n)(за рекурсивни повиквания)+O(1)(за други изчисления на постоянно време).

Решавайки горното уравнение, получаваме, че времевата сложност е O(loglogu).

Окончателно сортиране:Структурата Van Emde Boas може да се използва за сортиране, както е описано по-долу. Можем да вмъкнем всички елементи в структурата и да преминем през структурата, за да получим елементи в сортиран ред. Можем дори да извикаме функцията за намиране на наследник на първия елемент в структурата, за да получим втори елемент, и отново на втория елемент, за да получим трети елемент. Така можем да получим целия сортиран набор от числа. Всички тези изчисления включват извикване на функции, чиято времева сложност за една операция е O(loglogu). Когато се изпълнява за „n“ елементи, получаваме времева сложност като O(n*loglogu), което е много по-добро от O(nlogn). Следователно това е добър алгоритъм за сортиране на големи набори от данни.