Heap (datastruktur)

Datastrukturen heap, eller partiellt ordnat vänsterbalanserat träd, är 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).

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 roted som 0, har b^k noder. Första noden på nivån har position 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.

Notera att en heap för minnesallokering är en helt annan struktur, och att heapfunktioner i operativsystem i allmänhet avser den senare.

[redigera] Se även

• Stack
• Prioritetskö