Mound - pussel på nätet

Ett partiellt ordnat vänsterbalanserat träd (engelska: heap) är en datastruktur, närmare bestämt ett träd, som karakteriseras av att

varje nods värde är större eller lika med värdena i nodens barn (partiellt ordnat).

trädets grenar är så lika långa som möjligt. I fall det inte är möjligt så fylls den nedersta nivån på från vänster (vänsterbalanserat).Detta kallas ibland för en max-heap, alternativt kan man implementera en heap så att varje nods värde är mindre eller lika med nodens barns värden, en sådan heap kallas min-heap.

Namnet heap kommer från att det faktum att trädet är vänsterbalanserat gör det implementerbart i ett sammanhängande minnesområde, till exempel en minnesheap eller array. Nivå k i ett träd där varje nod har b barn, räknat med roten som 0, har

b

k

{\displaystyle b^{k}}

noder. Första noden på nivån har position

b

k

−

1

b

−

1

{\displaystyle {\frac {b^{k}-1}{b-1}}}

indexerat från 0. Alltså går det att räkna ut var i minnet en viss nod finns lagrad, om trädet har minst så många noder.

Detta i kombination med partiell ordning gör operationen att upprepade gånger "plocka" det största talet ur trädet billig, samtidigt som nya element och uppdateringar är effektiva. Den är därför lämplig som exempelvis prioritetskö för jobb.

Binär heap

I en binär heap har varje nod två barn, det vill säga att heapen är ett binärt träd.