trappa

(heap) – i programmering: sätt att ordna en priori­tets­kö, det vill säga att avgöra vilka data i minnet som ska be­arbe­tas först. Det är en datastruktur. – Man tänker sig minnet som en trappa där data (värden) med hög priori­tet ska finnas på översta trapp­steget (alltså först i kön). Värdena tilldelas prioritetsnivå innan de sänds till trappan. Ny­till­komna värden hamnar alltid på nedersta trappsteget, men om de då hamnar under ett värde med lägre prioritet så byter de två värdena plats. Detta upp­­repas trappsteg för trappsteg så många gånger som det behövs, så ett nytt värde kan i vissa fall smita förbi hela kön i trappan. – Man kan också beskriva trappan som en trädstruktur där värdena (prioritetsvärdena) är sorterade i storleksordning så att de högsta värdena är överst (närmast trädets rot). När trädet förgrenar sig ordnas grenarna i storleksordning efter grenens högsta värde, från vänster till höger (eller omvänt).

[datastrukturer] [ändrad 21 augusti 2019]