heap

En hög är en datastruktur som består av "noder" som innehåller värden. En typisk hög har en rot noden högst upp, som kan ha två eller flera underordnade noder direkt under den. Varje nod kan ha två eller flera barnnoder, vilket innebär att högen blir bredare för varje barnnod. När den visas visuellt ser en hög ut som ett upp och ned träd och den allmänna formen är en hög.

Medan varje nod i en hög kan ha två eller flera barnnoder (även kallad "barn"), begränsar de flesta högar varje nod till två barn. Dessa typer av högar kallas också binär högar och kan användas för att lagra sorterad data. Till exempel lagrar en "binär maxheap" det högsta värdet i rotnoden. Det andra och tredje högsta värdet lagras i undernoderna i rotnoden. I hela trädet har varje nod ett större värde än någon av dess underordnade noder. En "binär min hög" är motsatsen, där rotnoden lagrar det lägsta värdet och varje nod har ett lägre värde än sina underordnade.

Inom datavetenskap ritas högar ofta som enkla diagram. Att faktiskt lagra data i en hög är dock mer komplicerat. För att skapa en hög måste programmerare skriva individuellt algoritmer för att infoga och ta bort datum. Värdena infogade i en hög lagras vanligtvis i en array, som kan refereras till av en program. Eftersom data i en hög redan är sorterade ger det ett effektivt sätt att söka efter specifika värden.

OBS: "Heapen" är också en programmeringsterm som kan användas för att beskriva dynamiskt allokerad minne. Detta minnesblock kan nås via aktivt tillämpningar. Eftersom minnet i högen tilldelas dynamiskt kan det växa eller krympa beroende på hur mycket minne som används.