Случајан промешан хип

У информатици, случајни промешани хип (такође и промешани хип и случајан промешан приоритетни ред) је приоритетни ред. Случајни промешани хип је базична структура података у којој је основна структура такође хип-ред бинарно стабло. Како год, нема ограничења у облику основног бинарног стабла. Овај приступ има бројна побољшања у односу на сличне структуре података. Ова структура нуди сјајна поједностављења: све операције случајног промешаног хипа су лаке за имплементацију и константни фактори у њеној имплементацију су мали,такође нема потребе за чувањем услова баланса.

Операције

Случајан промешан хип подржава известан број заједничких операција. То су уметање,брисање,операција претраге,проналазак минимума. Операције уметања и брисања су имплементиране у терминима додатних специфичних операција за промешан хип , Promešaj(Q1,Q2).

Мешање

Основни циљ мешања(такође познатог као спајање)је да узмемо два хипа(узимајући од сваког хипа корен),Q1 и Q2 ,и спојити их,враћајући сам хип чвор као резултат. Добра одлика операције мешања је та да може бити дефинисана рекурзивно. Ако су оба хипа празна(показивач nil), тада метод једноставно враћа корен непразног хипа. Ако оба (и Q1 и Q2) нису nil ,проверити да ли је Q1>Q2. Ако јесте ,онда их заменимо. Због тога је сигурно да је Q1<Q2 и тај корен спојеног хипа ће садржати Q1. Онда рекурзивно спајамо Q2 са Q1.Levo или са Q1.Desno.

function Promešati(Čvor Q1, Čvor Q2)
 if Q1 je nil => return Q2
 if Q2 je nil => return Q1
 if Q1 > Q2 => zameni Q1 and Q2
 if bacanje_novčića je 0 => Q1.levo = Promešati(Q1.levo, Q2)
 else Q1.desno = Promešati(Q1.desno, Q2)
 return Q1

Уметање

Када је операција мешања завршена,уметање у промешан хип је једноставно. Прво,нови чвор,u,је креиран и садржи вредност x. Овај нови чвор је једноставно промешан са кореним чвором хипа.

function Umetanje(x)
 Čvor u = new Čvor
 u.x = x
 koren = Promešati(u, koren)
 r.roditelj = nil
 povećaj broj čvorova

Брисање

Слично као и код операције уметања.Brisanje() користи операцију мешања да елиминише корен из хипа.Ово се завршава мешањем два детета кореног чвора,и чвор који се враћа је нови корен.

function Brisanje()
 koren = Promešati(koren.levo, koren.desno)
 if koren nije nil => koren.roditelj = nil
 smanji broj čvorova

Налажење минимума

Вероватно најлакша операција за случајан промешан хип. NadjiMin() једноставно враћа елемент који је смештен у кореном чвору хипа.

Додатне операције

Неке додатне операције могу бити имплементиране за промешан хип, а да имају сложеност O(logn) у најгорем случају. Те операције су:

• Brisanje(u) - Брише све чворове у и њихове кључеве из хипа.
• Apsorbovanje(Q) - додаје све елементе хипа Q у овај хип,такодје празни Q у процесу
• SmanjenjeKljuča(u,y) - Смањује кључ у чвору са у на y (преуслов y<=у.x)

Анализа ефикасности

Како су све неконстантне временске операције дефинисане у терминима операције мешања, ефикасност ових операција може бити одредјена кроз анализу комплексности мешања два случајна хипа. Од резултата ове анализе се очекује да време операције било ког промешаног приоритетног реда на случајном хипу са n чворова буде O(log n).

Операције	Временска ефикасност најгорег случаја
Promešati(Q1, Q2)	O(logn)
Umetanje(x)	O(logn)
Brisanje()	O(logn)
NadjiMin()	O(logn)
Brisanje(x)	O(logn)
Apsorbovanje(Q)	O(logn)

Историја

Промешан хип је први пут предложен 1998. од стране Гамбина и Малинкоског.

Варијанте

Случајан промешан хип је најједноставнија форма имплементације промешаног хипа. Такође постоје и:

• Биномни хип
• Фибоначи хип