Софт хип

У рачунарству, софт хип је варијанта реда са приоритетом (хип структуре података). Ова структура података подржава уобичајене операције: Креирај, Уметни, Споји, Уклони и НадјиНајмањи. Његова предност је боља временска сложеност основних операција од логаритамске сложености коју имају у основној имплементацији хипа. То се постиже вештацким повећањем вредности одређених кључева хипа. Дат је било који скуп од н операција, софт хип са одступањем ε (за 0<ε<=1/2) осигурава да, у било које време, за свако ε*н, вредност клучева се повећава. Смањење сложености за све операције је константно, осим за операцију уметни, за коју је потребно О (лог(1/н)) времена. Софт хип је оптималан за било коју вредност ε у поређењу са основним хипом. Ова структура података је заснована на показивачу. Нису употребљени никакви низови нити су употребљене нумеричке претпоставке на овим кључевима. Основна идеја иза софт хипа је да се елементи померају по структури података не појединчно као што је уобичајено,већ у групама, тако да један утиче на остале. Као резултат овога кључеви морају бити повећани како би се сачувало својство хипа у структури података. Софт хип може да се користи за израчунавање тачне или приближне медијане и оптималне перцентиле (перцентил је мера корисности у статистици). Такође је користан за приближно сортирање као и проналажење минималног разапињућег стабла општих графова.

Операције

Списак операција

Ми ћемо направити једноставну варијанту реда са приоритером и назваћемо га софт хип. Ова структура података чува елементе са кључевима из потпуно уређеног скупа и подржава следеће операције:

• цреате(С): - операција креирај креира празан хип С
• инсерт(С, x): -операција уметни умеће елемент x у хип С
• мелд(С, С' ): -операција споји формира нови хип са садржајем хипа С и С' и уклони их након тога
• делете(С, x): -операција уклони(обриши) уклања елемент x из хипа С
• финдмин(С): -операција надји најмањи проналази елемент са најмањим кључем

Принцип функционисања Софт хипа

Софт хип може, у било ком тренутку, да повећа вредност одређених кључева. Такви кључеви, са увећаним вредностима, елементи који их садрже називају се ,,покварени". Поквареност је у потпуности одвојена од структуре података и зато корисник нема контролу над њим. Наравно, операција НадјиНајмањи (финдмин) враћа елемент са минималном вредношћу кључа, који би могао или не, бити покварен. Предност је брзина, током поправке хипа елементи путују заједно у пакетима у облику ,,шлеповања" како би уштедели време. Са информационо-теоријског становиста, кварење је начин да се смањи ентропија података ускладиштених у структури података и олакша поправљање. Ентропија је дефинисана као логаритам за основу два, броја различитих ,,посебних кључних задатака". Да би се видела битност ове идеје треба је максимално искористити и посматрати да ако се сваки кључ поквари тако сто се негова вредност постави на бесконачно онда група кључева има ентропију нула и можемо тривијално да извршимо све операције у константном времену. Занимљиво је да софт хип показује да ентропију не треба спустити на нулу да би сложеност постала константна.

Теорема: Почнимо без почетних података, размотримо мешавину секвенце операција н уметања. За било које ε где је 0<ε<=1/2, софт хип са одступањем ε обезбеђује да ће се свака операција извршити у константном времену, осим за операцију уметања, која захтева О(лог(1/н)) времена. Ова структура података никада не садржи више од ε*н ,,покварених елемената" за било које време. У поређењу са основним моделом ове границе су оптималне.

Напомена: Имајте на уму да то не значи да су само ε*н елементи ,,покварени" у ширем скупу операција. Захваљујући брисањима много више елемената се може покварити. Заправо, није тешко замислити ситуацју где су сви елементи покварени. Пример: убацивање н елемената и да се онда непрекидно бришу они који су ,,покварени". Упркос тој очигледној слабости, софт хип је оптималан и можда чак и изненађујуће користан.

Примене

Изненађујуће, упркос својим ограничењима и својој непредвидивој природи (енг.Нондетерминистиц алгоритхм), Софт хип је користан приликом конструкције алгоритама са детерминистичким понашањем(енг.Детерминистиц алгоритхм). Овај алгоритам се користи за постизање најбоље сложености приликом проналажења минималног разапињућег стабла. Могу се такође користити за лако правнљење селекционих алгоритама као и алгоритама за приближно сортирање (енг.неар-сортинг алгоритхмс), а то су алгоритми који постављају сваки елемент у близини његовог коначног положаја, а то је ситуација у којој је алгоритам сортирања уметањем брз. Један од најједноставнијих примера је сортирање избором. Рецимо да желимо да нађемо к-ти највећи елемент у групи од н бројева. Ми ћемо прво одабрати степен грешке од 1/3, што значи да ће највише 33% кључева елемената које унесемо бити покварено. Сада унесемо свих н елемената у хип - зваћемо оригиналне вредности "исправним кључевима", а вредности ускладиштене у хип "ускладиштеним кључевима". У овом тренутку највише н/3 кључева је покварено тј. највише н/3 ускладиштених елемената има кључ већи од исправног, а код свих осталих елемената је унесени кључ једнак исправном кључу. Даље, уклонимо минимални елемент из хипа н/3 пута (ово се ради у складу са ускладиштеним елементима). Како је укупан број уноса до сада н, још увек постоји највише н/3 покварених кључева у хипу. Сходно томе, најмање 2н/3 - н/3 = н/3 од кључева преосталих у хипу није покварено. Нека L буде елемент са највећим исправним кључем међу елементима које смо уклонили. Кључ у елементу L је вероватно већи од његовог исправног кључа (ако је L био покварен), па чак је и таква увећана вредност мања од унесених кључева елемената који су преостали у хипу (јер смо уклањали елементе са минималним кључем). Дакле, исправан кључ L је мањи од преосталих н/3 елемената који нису покварени у Софт хипу. Тако, L дели елементе негде између 33%/66% и 66%/33%. Затим ћемо поделити скуп коришћењем алгоритма партиционисања од QУИЦКСОРТ и применити исти алгоритам поново на скуп елемената мањих или скуп елемената већих од L, од којих ниједан не може прећи 2н/3 елемената. Посто свако уметање и брисање захтева О(1) времена, укупно детерминистичко време је Т(н)=Т(2н/3)+О(н). Користећи случај 3 у мастер теореми (са епсилон=1 и ц=2/3) ми знамо да је Т(н)=О(н). Коначан алгоритам изгледа овако:

Псеудо код алгоритма

 function softHeapSelect(a[1..n], k)
     if k = 1 then return minimum(a[1..n])
     create(S)
     for i from 1 to n
         insert(S, a[i])
     for i from 1 to n/3
         x := findmin(S)
         delete(S, x)
     xIndex := partition(a, x)  // Returns new index of pivot x
     if k < xIndex
         softHeapSelect(a[1..xIndex-1], k)
     else
         softHeapSelect(a[xIndex..n], k-xIndex+1)

Референце

• Цхазелле, Б. „Тхе софт хеап: ан аппроxимате приоритy qуеуе wитх оптимал еррор рате.”. 2000. ЦитеСеерX 10.1.1.5.9705 .  Ј. АЦМ 47, 6 (Нов. 2000), 1012-1027.
• Каплан, Х. анд Зwицк, У. 2009. А симплер имплементатион анд аналyсис оф Цхазелле'с софт хеапс. Ин Процеедингс оф тхе Нинетеентх Аннуал АЦМ -СИАМ Сyмпосиум он Дисцрете Алгоритхмс (Неw Yорк, Неw Yорк, Јануарy 4––6, 2009). Сyмпосиум он Дисцрете Алгоритхмс. Социетy фор Индустриал анд Апплиед Матхематицс, Пхиладелпхиа, ПА, 477-485.