Kopiec

Kopiec to struktura danych złożona z „węzłów” zawierających wartości. Typowy kopiec ma u góry węzeł korzenia, który może mieć bezpośrednio pod sobą dwa lub więcej węzłów potomnych. Każdy węzeł może mieć dwa lub więcej węzłów potomnych, co oznacza, że kopiec staje się szerszy przy każdym kolejnym poziomie. Wyświetlony w formie graficznej kopiec przypomina odwrócone drzewo, a jego ogólny kształt przypomina kopiec.

Chociaż każdy węzeł w kopcu może mieć dwa lub więcej węzłów potomnych (nazywanych także „dziećmi”), większość kopców ogranicza liczbę dzieci każdego węzła do dwóch. Takie kopce nazywa się także kopcami binarnymi i można ich używać do przechowywania posortowanych danych. Na przykład „binarny kopiec maksymalny” przechowuje największą wartość w węźle korzenia. Druga i trzecia pod względem wielkości wartość są przechowywane w węzłach potomnych korzenia. W całym drzewie każdy węzeł ma większą wartość niż którykolwiek z jego węzłów potomnych. „Binarny kopiec minimalny” działa odwrotnie — węzeł korzenia przechowuje najmniejszą wartość, a każdy węzeł ma mniejszą wartość niż jego dzieci.

W informatyce kopce często przedstawia się za pomocą prostych diagramów. Jednak rzeczywiste przechowywanie danych w kopcu jest bardziej złożone. Aby utworzyć kopiec, programiści muszą napisać osobne algorytmy do wstawiania i usuwania danych. Wartości wstawiane do kopca są zazwyczaj przechowywane w tablicy, do której może odwoływać się program. Ponieważ dane w kopcu są już posortowane, zapewnia on wydajny sposób wyszukiwania określonych wartości.

NOTE: „Sterta” to także termin programistyczny, którym można opisać dynamicznie przydzielaną pamięć. Ten blok pamięci może być używany przez aktywne aplikacje. Ponieważ pamięć na stercie jest przydzielana dynamicznie, sterta może rosnąć lub się kurczyć w zależności od ilości używanej pamięci.